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  dari sebuah monoid bebas , salah satunya dapat mendefinisikan himpunan yang terdiri dari kiri atau kanan formal invers dari elemen di .  Ini disebut hasil bagi, dan salah satunya dapat mendefinisikan hasil bagi kanan atau kiri, bergantung pada sisi mana yang digabungkan. Jadi, hasil bagi dari  oleh elemen  dari  adalah himpunan

Demikian pula, hasil bagi kiri adalah

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

Demikian pula, relasi sintaktik kiri adalah

Kekongruenan sintaktik atau kekongruenan Myhill dapat didefinisikan sebagai

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.

Mari kita sebut  kelas setara dari  untuk kekongruenan sintaktik.
kekongruenan sintaktik adalah serasi dengan penggabungan dalam monoid, yang satu memiliki

untuk . Jadi, hasil bagi sintaktiknya adalah morfisme monoid, dan menginduksi sebuah hasil bagi monoid

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

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

 

Bukti yang menunjukkan kesetaraan cukup mudah. Asumsi bahwa sebuah pengenalan automaton hingga  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 . Demikian, jumlah elemen di  paling banyak sama dengan jumlah status automata dan  adalah paling banyak jumlah status akhir. Asumsikan, sebaliknya, bahwa jumlah elemen dalam  terhingga. Salah satunya kemudian dapat membangun automaton di mana  adalah himpunan bagian,  adalah himpunan keadaan akhir, bahasa L merupakan keadaan awal, dan fungsi transisi diberikan oleh . Jelas, automaton ini mengenali  L . Jadi, bahasa  L  dikenali jika dan hanya jika disetel  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.

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

Referensi 

 
 
 
 
 
 

Bahasa formal
Teori semigrup