Contoh:
Aluran produksi
T -> a
T menghasilkan a
T menurunkan a
E -> T | T + E
- Tipe 0 UG (Unrestricted Grammar) Aturan:
- Ruas kiri harus min sebuah symbol variable
- Tidak ada batasan produksi
Ex:
Abc -> De = diterima
ABc -> e = diterima
abc -> AbdE = ditolak
aBcDe -> aBc = diterima
- Tipe 1 CSG (Conteks Sensitive)
Aturan:
- Simbol pada ruas sebelah kiri harus minimal ada sebuah simbol variable
- Panjang string pada ruas kiri ≤ pada ruas kanan |a|≤|B|
Ex:
Ab -> DeF = diterima
ABc -> EfG = diterima
AbcD -> ABc = ditolak
ab -> AbC = ditolak
- Tipe 2 CFG (Conteks Free Grammar)
Aturan: Kiri harus berupa sebuah simbol variable (non-terminal)
Ex:
B -> CDefG = diterima
ab -> AB = ditolak
Ab -> ABc = ditolak
a -> b = ditolak
- Tipe 3 RG (Regular Grammar)
Aturan:
- Simbol pada sebelah kiri harus berupa sebuah simbol variable.
- Simbol pada sebelah kanan maksimal hanya memiliki sebuah simbol variable dan bila ada terletak diposisi paling kanan.
Ex:
A -> C = diterima
AbC -> eFgh = ditolak
ABc -> efg = ditolak
A -> aBcD = ditolak
A -> abCD = ditolak
Ab -> abC = ditolak
B -> Bc = ditolak
