Jelaskan Kesetaraan sintaktik dari Monoid 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.