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 sunting

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 $S$ dari sebuah monoid bebas $M$ , salah satunya dapat mendefinisikan himpunan yang terdiri dari kiri atau kanan formal invers dari elemen di $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 $S$ oleh elemen $m$ dari $M$ adalah himpunan

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

Demikian pula, hasil bagi kiri adalah

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

Kesetaraan sintaktik sunting

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

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

Demikian pula, relasi sintaktik kiri adalah

{}_{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]

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 $[s]_{S}$ kelas setara dari $s$ untuk kekongruenan sintaktik. kekongruenan sintaktik adalah serasi dengan penggabungan dalam monoid, yang satu memiliki

[s]_{S}[t]_{S}=[st]_{S}

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

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

Monoid $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

\{m\setminus L\,\vert \;m\in M\}

^[1]

Bukti yang menunjukkan kesetaraan cukup mudah. Asumsi bahwa sebuah pengenalan automaton hingga $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 $x\setminus L\,=y\setminus L$ . Demikian, jumlah elemen di $\{m\setminus L\,\vert \;m\in M\}$ paling banyak sama dengan jumlah status automata dan $\{m\setminus L\,\vert \;m\in L\}$ adalah paling banyak jumlah status akhir. Asumsikan, sebaliknya, bahwa jumlah elemen dalam $\{m\setminus L\,\vert \;m\in M\}$ terhingga. Salah satunya kemudian dapat membangun automaton di mana $Q=\{m\setminus L\,\vert \;m\in M\}$ adalah himpunan bagian, $F=\{m\setminus L\,\vert \;m\in L\}$ adalah himpunan keadaan akhir, bahasa L merupakan keadaan awal, dan fungsi transisi diberikan oleh $y\setminus (x\setminus L)=(xy)\setminus L$ . Jelas, automaton ini mengenali L . Jadi, bahasa L dikenali jika dan hanya jika disetel $\{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 sunting

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 sunting

^ ^a ^b ^c Holcombe (1982) p.160
^ ^a ^b Lawson (2004) p.210
^ Lawson (2004) p.232
^ Straubing (1994) p.55
^ ^a ^b Sakarovitch (2009) p.342
^ Straubing (1994) p.54
^ ^a ^b McNaughton, Robert; Papert, Seymour (1971). Counter-free Automata . Research Monograph. 65. With an appendix by William Henneman. MIT Press. hlm. 48. ISBN 0-262-13076-9. Zbl 0232.94024.
^ Lawson (2004) p.233
^ Marcel-Paul Schützenberger (1965). "On finite monoids having only trivial subgroups" (PDF). Information and Computation. 8 (2): 190–194. doi:10.1016/s0019-9958(65)90108-7.
^ Straubing (1994) p.60

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.

[Hol160-1] Holcombe (1982) p.160

[Law210-2] Lawson (2004) p.210

[Law232-3] Lawson (2004) p.232

[S55-4] Straubing (1994) p.55

[Sak342-5] Sakarovitch (2009) p.342

[S54-6] Straubing (1994) p.54

[MP48-7] McNaughton, Robert; Papert, Seymour (1971). Counter-free Automata . Research Monograph. 65. With an appendix by William Henneman. MIT Press. hlm. 48. ISBN 0-262-13076-9. Zbl 0232.94024.

[Law233-8] Lawson (2004) p.233

[9] Marcel-Paul Schützenberger (1965). "On finite monoids having only trivial subgroups" (PDF). Information and Computation. 8 (2): 190–194. doi:10.1016/s0019-9958(65)90108-7.

[S60-10] Straubing (1994) p.60

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]