Monoid 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+., 

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

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.

 Contoh 

 Bilangan asli 
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
Karena penambahan bilangan asli bersifat asosiatif, hasilnya tidak bergantung pada urutan evaluasi, sehingga memastikan pemetaan terdefinisi dengan baik.
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 
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, , ...}.

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.Sakarovitch (2009) p.382 (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.

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 
Kami mendefinisikan sepasang kata dalam A∗ dari bentuk  uv  dan  vu  sebagai  'konjugasi' : konjugasi sebuah kata adalah pergeseran melingkar-nya.Sakarovitch (2009) p.27  Dua kata dikonjugasikan dalam pengertian ini jika mereka konjugasi dalam pengertian teori grup sebagai elemen dari grup bebas yang dihasilkan oleh A.

 Ekuidivisibilitas 
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.Sakarovitch (2009) p.26 Hasil ini juga dikenal sebagai lemma Levi.

Sebuah monoid bebas jika dan hanya jika bertingkat dan equidivisible.

 Faktorisasi 

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 
Perpotongan submonoids bebas dari monoid bebas A∗ is again free.  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 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 
Endomorfisme pada A∗ adalah morfisme dari A∗ to itself.  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 .Allouche & Shallit (2003) p.10

 Proyeksi pita 
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 
 Operasi pita

 Catatan 

 Referensi 









 Pranala luar 

Kategori:Teori semigrup
Kategori:Bahasa formal
Kategori:Struktur aljabar gratis
Kategori:Kombinatorik pada kata-kata