Grammar pada Teori Bahasa Otomata

Grammar Klas 0 :
Unrestricted Grammar : Aturan-aturan sintaktik (productions) yang digunakan untuk membentuk kalimat tidak mempunyai batasan yang jelas.
Contoh :
G = ({S, A, B, C, D}, {a, b}, S, q), dengan q adalah :
S ® CD Aa ® aA C ® e
C ® aCA | bCB Ab ® bA D ® e
AD ® aD Ba ® aB
BD ® bD Bb ® bB
Bahasa yang didefinisikan grammar di atas adalah :
L(G) = { ww | w Î {a, b}}
Grammar Klas 2 :
Context-Free Grammar (CFG) : Grammar dengan production yang berbentuk a ® b, dimana |a| £ |b| dengan a Î Vn dan |a| = 1. Dengan demikian, production-production pada klas grammar ini hanya memiliki satu non-terminal di sisi kiri setiap productionnya. Bahasa yang didefinisikan oleh CFG ini disebut Context-Free Language.
CFG merupakan satu-satunya klas grammar yang telah memiliki algoritma parsing yang optimal. Sehingga hampir semua bahasa pemrograman menggunakan CFG untuk mendefinifikan aturan-aturan sintaktik bahasanya.
Contoh : Bahasa = { an b an | n ³ 1 } didefinisikan melalui grammar berikut :
S ® aCa
C ® aCa | b
Derivasi untuk input string a3 b a3 adalah sebagai berikut :
S Þ aCa Þ aaCaa Þ aaaCaaa Þ aaabaaa
Grammar Klas 3 :
Regular Grammar : Grammar dengan production yang berbentuk a ® b, dimana |a| £ |b| dengan a Î Vn dan |a| = 1. Sedangkan b mempunyai bentuk aB atau a (a Î VT dan B Î VN). Bahasa yang didefinisikan oleh Regular Grammar ini disebut Regular Language.
Bahasa pemrograman yang menggunakan aturan sintaktik bahasa regular ini antara lain adalah javascript, perl, dll.
Contoh : Bahasa = { an b am | n ³ 1 } didefinisikan melalui grammar berikut :
S ® aS | aB
C ® aC | a
B ® bC
Derivasi untuk input string a3 b a2 adalah sebagai berikut :
S Þ aS Þ aaS Þ aaaB Þ aaabC Þ aaabaC Þ aaabaa