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  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
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 [[John Myhill|Myhill]]** dapat didefinisikan sebagai

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

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

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

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

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.

## 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*1, kata-kata yang panjangnya ganjil. Monoid sintaktik adalah grup tingkat 2  {*L*,*L*1}.  
* 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 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 2*n* adalah bagian kelompok dengan monoid sintaktik **Z**/2*n*.
* Monoid teras adalah contoh dari monoid sintaktik.
* Marcel-Paul Schützenberger ditandai bahasa bebas bintang sebagai bahasa dengan monoid sintaktik takberkala hingga.

## Referensi

* 
* 
* 
* 
* 
*