Lompat ke isi

Monoid bebas

Dari Wikipedia bahasa Indonesia, ensiklopedia bebas
(Dialihkan dari Semigrup bebas)

Dalam aljabar abstrak, monoid bebas pada himpunan adalah monoid yang semua elemennya adalah urutan hingga (atau string) dari nol atau lebih elemen dari himpunan, dengan penggabungan pita sebagai operasi monoid dan dengan urutan unik elemen nol, sering disebut pita kosong dan dilambangkan dengan ε atau λ, sebagai elemen identitas. Monoid bebas pada himpunan A biasanya dilambangkan A. Semigrup bebas di A adalah subsemigrup dari A mengandung semua elemen kecuali string kosong. Biasanya dilambangkan A+.[1][2]

Secara lebih umum, sebuah monoid abstrak (atau setengah grup) S dideskripsikan sebagai bebas jika isomorfik ke monoid bebas (atau semigroup) pada beberapa set.[3]

Sesuai dengan namanya, monoid dan semigroup bebas adalah objek yang memenuhi sifat universal yang biasa mendefinisikan objek bebas, di masing-masing kategori dari monoid dan semigroup. Oleh karena itu, setiap monoid (atau semigrup) muncul sebagai citra homomorfik dari monoid bebas (atau semigrup). Studi tentang semigroup sebagai gambar dari semigrup bebas disebut teori semigroup kombinatorial.

Monoid bebas (dan monoid pada umumnya) adalah asosiatif, menurut definisi; artinya, mereka ditulis tanpa tanda kurung untuk menunjukkan pengelompokan atau urutan operasi. Padanan non-asosiatifnya adalah magma bebas.

Bilangan asli

[sunting | sunting sumber]

Monoid (N0,+) dari bilangan asli (termasuk nol) yang ditambahkan adalah monoid bebas pada generator bebas tunggal, dalam hal ini bilangan asli 1. Menurut definisi formalnya, monoid ini terdiri dari semua urutan seperti "1", "1 + 1", "1 + 1 + 1", "1 + 1 + 1 + 1", dan seterusnya, termasuk barisan kosong. Memetakan setiap urutan tersebut ke hasil evaluasinya [4] dan urutan kosong ke nol membentuk isomorfisme dari himpunan urutan tersebut ke N0. Isomorfisma ini kompatibel dengan "+", yaitu, untuk dua urutan s dan t , jika s dipetakan (yaitu dievaluasi) ke nomor m dan t ke n, untuk rangkaian s+t

Bintang Kleene

[sunting | sunting sumber]

Dalam teori bahasa formal, biasanya serangkaian "simbol" A (kadang-kadang disebut alfabet) dianggap terbatas. Urutan simbol yang terbatas disebut "kata di atas A ", dan monoid bebas A disebut "Bintang Kleene dari A ". Dengan demikian, studi abstrak bahasa formal dapat dianggap sebagai studi subset dari monoid bebas yang dihasilkan tanpa batas.

Misalnya, dengan asumsi alfabet A = {a, b, c}, bintang Kleene-nya A berisi semua rangkaian a, b, dan c:

{ε, a, ab, ba, caa, cccbabbc, ...}.

Jika A ada yang disetel, fungsi panjang kata aktif A adalah homomorfisme monoid dari A ke (N0,+) yang memetakan setiap elemen A ke 1. Monoid bebas dengan demikian adalah monoid bertingkat.[5] (Sebuah monoid bertingkat adalah sebuah monoid yang dapat ditulis sebagai . Setiap adalah sebuah nilai; penilaian di sini hanyalah panjang string. Artinya, berisi string dengan panjang tersebut The simbol di sini dapat diartikan "mengatur persatuan"; ini digunakan sebagai pengganti simbol karena, secara umum, set union mungkin bukan monoid, dan simbol yang berbeda digunakan. Sesuai ketentuan, gradasi selalu ditulis dengan simbol .)

Ada hubungan yang dalam antara teori semigrup dan automata. Misalnya, setiap bahasa formal memiliki monoid sintaktik yang mengenali bahasa tersebut. Untuk kasus bahasa reguler, monoid itu isomorfik ke transisi monoid yang terkait dengan semiautomaton dari beberapa automaton terbatas deterministik yang mengenali bahasa. Bahasa reguler di atas alfabet A adalah penutupan dari himpunan bagian hingga A*, monoid bebas di atas A, di bawah penyatuan, produk, dan pembuatan submonoid.[6]

Untuk kasus komputasi serentak, yaitu, sistem dengan kunci, mutex atau benang gabungan, komputasi dapat dijelaskan dengan sejarah monoid dan jejak monoid. Secara kasar, elemen monoid dapat melakukan perjalanan, (mis, utas yang berbeda dapat dijalankan dalam urutan apa pun), tetapi hanya hingga kunci atau mutex, yang mencegah pergantian lebih lanjut (mis, membuat serial akses utas ke beberapa objek).

Kata konjugasi

[sunting | sunting sumber]
Contoh untuk kasus pertama ekuidivisibilitas: m="UNCLE", n="ANLY", p="UN", q="CLEANLY", dan s="CLE"

Kami mendefinisikan sepasang kata dalam A dari bentuk uv dan vu sebagai 'konjugasi' : konjugasi sebuah kata adalah pergeseran melingkar-nya.[7] Dua kata dikonjugasikan dalam pengertian ini jika mereka konjugasi dalam pengertian teori grup sebagai elemen dari grup bebas yang dihasilkan oleh A.[8]

Ekuidivisibilitas

[sunting | sunting sumber]

Monoid bebas adalah equidivisible: jika persamaan mn = pq berlaku, maka terdapat s sehingga m = ps, sn = q (contoh lihat gambar) atau ms = p, n = sq.[9] Hasil ini juga dikenal sebagai lemma Levi.[10]

Sebuah monoid bebas jika dan hanya jika bertingkat dan equidivisible.[9]

Faktorisasi

[sunting | sunting sumber]

Faktorisasi dari monoid bebas adalah urutan himpunan bagian kata dengan sifat bahwa setiap kata dalam monoid bebas dapat dituliskan sebagai rangkaian elemen yang diambil dari himpunan bagian tersebut. Teorema Chen–Fox–Lyndon menyatakan bahwa Kata Lyndon memberikan faktorisasi. Secara lebih umum, Kata Hall memberikan faktorisasi; kata-kata Lyndon adalah kasus khusus dari kata-kata Hall.

Lambung bebas

[sunting | sunting sumber]

Perpotongan submonoids bebas dari monoid bebas A is again free.[11][12] Jika S adalah himpunan bagian dari monoid bebas A * maka perpotongan semua submonoid bebas dari A * yang mengandung S terdefinisi dengan baik, karena A * sendiri bebas, dan mengandung S ; itu adalah monoid bebas dan disebut lambung bebas dari S. Basis dari persimpangan ini adalah sebuah kode.

Teorema cacat[11][12][13] menyatakan bahwa jika X terbatas dan C adalah dasar dari lambung bebas X , maka salah satu X adalah kode dan C = X , atau

|C| ≤ |X| − 1 .

Endomorfisme

[sunting | sunting sumber]

Endomorfisme pada A adalah morfisme dari A to itself.[14] Peta identitas I adalah endomorfisme dari A, dan endomorfisme membentuk monoid di bawah komposisi fungsi.

Endomorfisme f adalah perpanjangan jika ada huruf a sedemikian rupa sehingga f(a) = as untuk pita yang tidak kosong s .[15]

Proyeksi pita

[sunting | sunting sumber]

Operasi dari proyeksi pita adalah sebuah endomorfisme. Artinya, diberi rumus a ∈ Σ dan seutas pita s ∈ Σ, proyeksi pita pa(s) menghapus setiap kemunculan a dari s ; itu secara formal didefinisikan oleh

Perhatikan bahwa proyeksi pita terdefinisi dengan baik bahkan jika peringkat monoid tidak terbatas, karena definisi rekursif di atas berfungsi untuk semua string dengan panjang terbatas. Proyeksi pita adalah morfisme dalam kategori monoid bebas, sehingga

dimana dipahami sebagai monoid bebas dari semua pita berhingga yang tidak mengandung huruf a . Proyeksi bolak-balik dengan pengoperasian rangkaian pita, sehingga untuk semua string s dan t . Ada banyak pembalikan kanan untuk proyeksi string, dan karenanya ini adalah epimorfisme terpisah.

Morfisme identitas adalah didefinisikan sebagai untuk pita 's', dan .

Proyeksi pita bersifat komutatif, dengan jelas

Untuk monoid bebas dengan pangkat terbatas, ini mengikuti dari fakta bahwa monoid bebas dengan pangkat yang sama bersifat isomorfik, karena proyeksi mengurangi pangkat monoid satu per satu.

Proyeksi pita adalah idempoten, sebagai

untuk pita s. Jadi, proyeksi adalah operasi idempoten, komutatif, dan karenanya membentuk semilatik berbatas atau komutatif band.

Lihat pula

[sunting | sunting sumber]
  1. ^ (Lothaire 1997, hlm. 2–3), [1]
  2. ^ (Pytheas Fogg 2002, hlm. 2)
  3. ^ (Lothaire 1997, hlm. 5)
  4. ^ Karena penambahan bilangan asli bersifat asosiatif, hasilnya tidak bergantung pada urutan evaluasi, sehingga memastikan pemetaan terdefinisi dengan baik.
  5. ^ Sakarovitch (2009) p.382
  6. ^ Borovik, Alexandre (2005-01-01). Groups, Languages, Algorithms: AMS-ASL Joint Special Session on Interactions Between Logic, Group Theory, and Computer Science, January 16-19, 2003, Baltimore, Maryland (dalam bahasa Inggris). American Mathematical Soc. ISBN 9780821836187. 
  7. ^ Sakarovitch (2009) p.27
  8. ^ (Pytheas Fogg 2002, hlm. 297)
  9. ^ a b Sakarovitch (2009) p.26
  10. ^ Aldo de Luca; Stefano Varricchio (1999). Finiteness and Regularity in Semigroups and Formal Languages. Springer Berlin Heidelberg. hlm. 2. ISBN 978-3-642-64150-3. 
  11. ^ a b (Lothaire 1997, hlm. 6)
  12. ^ a b (Lothaire 2011, hlm. 204)
  13. ^ (Berstel, Perrin & Reutenauer 2010, hlm. 66)
  14. ^ (Lothaire 2011, hlm. 450)
  15. ^ Allouche & Shallit (2003) p.10

Referensi

[sunting | sunting sumber]

Pranala luar

[sunting | sunting sumber]