Monoid sintaktik

Dalam matematika dan ilmu komputer, monoid sintaktik M(L) dari bahasa formal L adalah monoid terkecil yang mengenali bahasa L .

Hasil bagi sintaktik

Monoid bebas pada suatu himpunan adalah monoid yang elemen-elemennya adalah semua untai dari nol atau lebih elemen dari himpunan, dengan rangkaian untai sebagai operasi monoid dan untai kosong sebagai elemen identitas. Diberikan himpunan bagian ${\displaystyle S}$ dari sebuah monoid bebas ${\displaystyle M}$, salah satunya dapat mendefinisikan himpunan yang terdiri dari kiri atau kanan formal invers dari elemen di ${\displaystyle S}$. Ini disebut hasil bagi, dan salah satunya dapat mendefinisikan hasil bagi kanan atau kiri, bergantung pada sisi mana yang digabungkan. Jadi, hasil bagi dari ${\displaystyle S}$ oleh elemen ${\displaystyle m}$ dari ${\displaystyle M}$ adalah himpunan

${\displaystyle S\ /\ m=\{u\in M\;\vert \;um\in S\}.}$

Demikian pula, hasil bagi kiri adalah

${\displaystyle m\setminus S=\{u\in M\;\vert \;mu\in S\}.}$

Kesetaraan sintaktik

Hasil bagi sintaktik menginduksi sebuah relasi setara pada M , yang disebut relasi sintaktik, atau kesetaraan sintaktik (diinduksi oleh S ). Kesetaraan sintaktik yang tepat adalah hubungan kesetaraan

${\displaystyle \sim _{S}\;=\{(s,t)\in M\times M\,\vert \;S\ /\ s=S\ /\ t\}.}$

Demikian pula, relasi sintaktik kiri adalah

${\displaystyle {}_{S}{\sim }\,=\{(s,t)\in M\times M\,\vert \;s\setminus S=t\setminus S\}.}$

Kekongruenan sintaktik atau kekongruenan Myhill^[1] dapat didefinisikan sebagai^[2]

${\displaystyle s\equiv _{S}t\Leftrightarrow \forall x,y\in M(xsy\in S\Leftrightarrow xty\in S).}$

Definisi tersebut meluas ke kekongruenan yang didefinisikan oleh himpunan bagian S dari monoid umum M. Himpunan terpisah adalah himpunan bagian S sedemikian rupa sehingga kekongruenan sintaktik yang didefinisikan oleh S adalah relasi kesetaraan.^[3]

Mari kita sebut ${\displaystyle [s]_{S}}$ kelas setara dari ${\displaystyle s}$ untuk kekongruenan sintaktik. kekongruenan sintaktik adalah serasi dengan penggabungan dalam monoid, yang satu memiliki

${\displaystyle [s]_{S}[t]_{S}=[st]_{S}}$

untuk ${\displaystyle s,t\in M}$. Jadi, hasil bagi sintaktiknya adalah morfisme monoid, dan menginduksi sebuah hasil bagi monoid

${\displaystyle M(S)=M\ /\ {\equiv _{S}}.}$

Monoid ${\displaystyle M(S)}$ ini disebut monoid sintaktik dari S . Dapat ditunjukkan bahwa itu adalah monoid terkecil yang mengenali S ; yaitu, M(S) mengenali S, dan untuk setiap monoid N mengenali S, M(S) adalah hasil bagi dari submonoid dari N. Monoid sintaktik dari S juga merupakan monoid transisi dari automata minimal dari S .^[1][2][4]

Demikian pula, bahasa L biasa jika dan hanya jika rumpun quotients

${\displaystyle \{m\setminus L\,\vert \;m\in M\}}$^[1]

Bukti yang menunjukkan kesetaraan cukup mudah. Asumsi bahwa sebuah pengenalan automaton hingga ${\displaystyle L}$ membaca masukan x yang mengarah untuk menyatakan p. Jika y adalah untai lain yang dibaca oleh mesin, juga diakhiri dalam status yang sama p , maka jelas ${\displaystyle x\setminus L\,=y\setminus L}$. Demikian, jumlah elemen di ${\displaystyle \{m\setminus L\,\vert \;m\in M\}}$ paling banyak sama dengan jumlah status automata dan ${\displaystyle \{m\setminus L\,\vert \;m\in L\}}$ adalah paling banyak jumlah status akhir. Asumsikan, sebaliknya, bahwa jumlah elemen dalam ${\displaystyle \{m\setminus L\,\vert \;m\in M\}}$ terhingga. Salah satunya kemudian dapat membangun automaton di mana ${\displaystyle Q=\{m\setminus L\,\vert \;m\in M\}}$ adalah himpunan bagian, ${\displaystyle F=\{m\setminus L\,\vert \;m\in L\}}$ adalah himpunan keadaan akhir, bahasa L merupakan keadaan awal, dan fungsi transisi diberikan oleh ${\displaystyle y\setminus (x\setminus L)=(xy)\setminus L}$. Jelas, automaton ini mengenali L . Jadi, bahasa L dikenali jika dan hanya jika disetel ${\displaystyle \{m\setminus L\,\vert \;m\in M\}}$ adalah hingga. Perhatikan bahwa buktinya juga membangun automaton minimal.

Diberikan ekspresi reguler E yang mewakili S , maka mudah untuk menghitung monoid sintaktik dari S .

bahasa grup adalah salah satu yang monoid sintaktiknya adalah grup.^[5]

Contoh

• Misalkan L menjadi bahasa atas A = {a,b} mengenai kata-kata yang panjangnya genap. kekongruenan sintaktik memiliki dua kelas, L itu sendiri dan L₁, kata-kata yang panjangnya ganjil. Monoid sintaktik adalah grup tingkat 2 {L,L₁}.^[6]
• Monoid bisiklik adalah monoid sintaktik dari bahasa Dyck (bahasa kumpulan tanda kurung yang seimbang).
• Monoid bebas pada A (|A| > 1) adalah monoid sintaktik { ww^R | w in A* }, dimana w^R menunjukkan pembalikan kata w .
• Setiap monoid berhingga bersifat homomorfik^{[butuh klarifikasi]} ke monoid sintaktik dari beberapa bahasa taktrivial,^[7] tetapi tidak setiap monoid hingga isomorfik ke monoid sintaktik.^[8]
• Setiap grup berhingga isomorfik dengan monoid sintaktik dari beberapa taktrivial.^[7]
• Bagian terakhir {a,b} di mana jumlah kemunculan a dan b adalah modulo kongruen 2ⁿ adalah bagian kelompok dengan monoid sintaktik Z/2ⁿ.^[5]
• Monoid teras adalah contoh dari monoid sintaktik.
• Marcel-Paul Schützenberger^[9] ditandai bahasa bebas bintang sebagai bahasa dengan monoid sintaktik takberkala hingga.^[10]

Referensi

• Anderson, James A. (2006). Automata theory with modern applications. With contributions by Tom Head. Cambridge: Cambridge University Press. ISBN 0-521-61324-8. Zbl 1127.68049. 
• Holcombe, W.M.L. (1982). Algebraic automata theory. Cambridge Studies in Advanced Mathematics. 1. Cambridge University Press. ISBN 0-521-60492-3. Zbl 0489.68046. 
• Lawson, Mark V. (2004). Finite automata. Chapman and Hall/CRC. ISBN 1-58488-255-7. Zbl 1086.68074. 
• Pin, Jean-Éric (1997). "10. Syntactic semigroups". Dalam Rozenberg, G.; Salomaa, A. Handbook of Formal Language Theory (PDF). 1. Springer-Verlag. hlm. 679–746. Zbl 0866.68057. 
• Sakarovitch, Jacques (2009). Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge University Press. ISBN 978-0-521-84425-3. Zbl 1188.68177. 
• Straubing, Howard (1994). Finite automata, formal logic, and circuit complexity. Progress in Theoretical Computer Science. Basel: Birkhäuser. ISBN 3-7643-3719-2. Zbl 0816.68086.