HIRARKI CHOMSKY

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