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⁺.^[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.

Monoid (N₀,+) 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 N₀. 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

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 (N₀,+) yang memetakan setiap elemen A ke 1. Monoid bebas dengan demikian adalah monoid bertingkat.^[5] (Sebuah monoid bertingkat ${\displaystyle M}$ adalah sebuah monoid yang dapat ditulis sebagai ${\displaystyle M=M_{0}\oplus M_{1}\oplus M_{2}\cdots }$. Setiap ${\displaystyle M_{n}}$ adalah sebuah nilai; penilaian di sini hanyalah panjang string. Artinya, ${\displaystyle M_{n}}$ berisi string dengan panjang tersebut ${\displaystyle n.}$ The ${\displaystyle \oplus }$ simbol di sini dapat diartikan "mengatur persatuan"; ini digunakan sebagai pengganti simbol ${\displaystyle \cup }$ karena, secara umum, set union mungkin bukan monoid, dan simbol yang berbeda digunakan. Sesuai ketentuan, gradasi selalu ditulis dengan simbol ${\displaystyle \oplus }$.)

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).

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]

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 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.

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 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]

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

${\displaystyle p_{a}(s)={\begin{cases}\varepsilon &{\text{jika }}s=\varepsilon ,{\text{ pita kosong}}\\p_{a}(t)&{\text{jika }}s=ta\\p_{a}(t)b&{\text{jika }}s=tb{\text{ dan }}b\neq a.\end{cases}}}$

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

${\displaystyle p_{a}\left(\Sigma ^{*}\right)=\left(\Sigma -a\right)^{*}}$

dimana ${\displaystyle p_{a}\left(\Sigma ^{*}\right)}$ dipahami sebagai monoid bebas dari semua pita berhingga yang tidak mengandung huruf a . Proyeksi bolak-balik dengan pengoperasian rangkaian pita, sehingga ${\displaystyle p_{a}(st)=p_{a}(s)p_{a}(t)}$ untuk semua string s dan t . Ada banyak pembalikan kanan untuk proyeksi string, dan karenanya ini adalah epimorfisme terpisah.

Morfisme identitas adalah ${\displaystyle p_{\varepsilon },}$ didefinisikan sebagai ${\displaystyle p_{\varepsilon }(s)=s}$ untuk pita 's', dan ${\displaystyle p_{\varepsilon }(\varepsilon )=\varepsilon }$.

Proyeksi pita bersifat komutatif, dengan jelas

${\displaystyle p_{a}(p_{b}(s))=p_{b}(p_{a}(s)).}$

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

${\displaystyle p_{a}(p_{a}(s))=p_{a}(s)}$

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

• Operasi pita

• Allouche, Jean-Paul; Shallit, Jeffrey (2003), Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, ISBN 978-0-521-82332-6, Zbl 1086.11015 
• Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010), Codes and automata, Encyclopedia of Mathematics and its Applications, 129, Cambridge: Cambridge University Press, ISBN 978-0-521-88831-8, Zbl 1187.94001 
• Lothaire, M. (1997), Combinatorics on words, Cambridge Mathematical Library, 17, Contributors: Perrin, D.; Reutenauer, C.; Berstel, J.; Pin, J. E.; Pirillo, G.; Foata, D.; Sakarovitch, J.; Simon, I.; Schützenberger, M. P.; Choffrut, C.; Cori, R. Series editors: Lyndon, Roger; Rota, Gian-Carlo. Foreword by Roger Lyndon (edisi ke-2nd), Cambridge University Press, doi:10.1017/CBO9780511566097, ISBN 0-521-59924-5, MR 1475463, Zbl 0874.20040 
• Lothaire, M. (2011), Algebraic combinatorics on words, Encyclopedia of Mathematics and Its Applications, 90, With preface by Jean Berstel and Dominique Perrin (edisi ke-Reprint of the 2002 hardback), Cambridge University Press, ISBN 978-0-521-18071-9, Zbl 1221.68183 
• Lothaire, M. (2005), Applied combinatorics on words, Encyclopedia of Mathematics and Its Applications, 105, A collective work by Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, Gesine Reinert, Sophie Schbath, Michael Waterman, Philippe Jacquet, Wojciech Szpankowski, Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche and Valérie Berthé, Cambridge: Cambridge University Press, ISBN 0-521-84802-4, Zbl 1133.68067 
• Pytheas Fogg, N. (2002), Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A., ed., Substitutions in dynamics, arithmetics and combinatorics, Lecture Notes in Mathematics, 1794, Berlin: Springer-Verlag, ISBN 3-540-44141-7, Zbl 1014.11015 
• Sakarovitch, Jacques (2009), Elements of automata theory, Translated from the French by Reuben Thomas, Cambridge: Cambridge University Press, ISBN 978-0-521-84425-3, Zbl 1188.68177 
• Salomaa, Arto (1981), Jewels of Formal Language Theory, Pitman Publishing, ISBN 0-273-08522-0, Zbl 0487.68064 

• Media tentang Free monoid di Wikimedia Commons