Hirarki Chomsky

Pada tahun 1959, seorang ahli bernama Noam Chomsky melakukan penggolongan tingkatan bahasa menjadi empat, yang disebut dengan hirarki Chomsky. Penggolongan tersebut bisa dilihat pada tabel berikut :

• Secara umum tata bahasa dirumuskan sebagai berikut : α→β, yang berarti α menghasilkan β atau α menurunkan β. 

Di mana α menyatakan simbol-simbol pada ruas kiri aturan produksi (sebelah kiri tanda ‘→’) dan β menyatakan simbol-simbol pada ruas kanan aturan produksi (sebelah kanan tanda‘→’)

• Simbol variabel / non terminal adalah simbol yang masih bisa diturunkan dan ditandai dengan huruf besar sepertiA, B, C, dst.
• Simbol terminal adalah simbol yang sudah tidak bisa diturunkan dan ditandai dengan huruf kecil seperti a,b,c,dst.

Contoh Aturan Produksi

• T → a
  dibaca "T menghasilkan a"
• E →T | T + E  
  dibaca "E menghasilkan T" atau "E menghasilkan T dan E"

Simbol | menyatakan‘atau’, digunakan untuk mempersingkat penulisan aturan produksi yang mempunyai ruas kiri yang sama.

1. Tipe 0 / Unrestricted / Natural Language 
   Aturan : 
1. Simbol pada ruas sebelah kiri harus minimal ada sebuah simbol variabel 
2. Tidak ada batasan pada aturan produksinya.
   Misal : 
• Abc → De (diterima) 
• ABC → b (diterima) 
• abc → GHI (ditolak, karena simbol pada sebelahkiri tidak ada sebuah simbol variabel)
  
  
2. Tipe 1 / Conteks Sensitive 
   Aturan : 
1. Simbol pada ruas sebelah kiri harus minimal ada sebuah simbol variable
2. Panjang string pada ruas kiri ≤ panjang string pada ruas kanan |α | ≤ |β|. 
   Misal : 
• Ab → DeF (diterima)
• CD → eF (diterima) exception : S → ε (diterima) 
• ABC → DE (ditolak, karena jumlah simbol pada ruas sebelah kiri lebih bayak dari jumlah simbol pada ruas kanan)
  
  
3. Tipe 2 / Bebas Konteks / Context Free 
   Aturan : 
1. Simbol pada Sebelah kiri harus berupa sebuah simbol variable 
   Misal : 
• B → CDeFG (diterima) 
• D → BcDe (diterima) 
• a → b (Ditolak, karena simbol pada sebelah kiri harus berupa sebuah simbol variabel)
4. Tipe 3/ Reguler 
   Aturan : 
1. Simbol pada Sebelah kiri harus berupa sebuah simbol variabel 
2. Simbol pada sebelah kanan maksimal hanya memiliki sebuah simbol variabel dan bila ada terletak di posisi paling kanan. 
   Misal : 
• A  → e (diterima) 
• A  → fgh (diterima)
• A  → eH (diterima) 
• C → D (diterima) 
• A → Bc (Ditolak, karena simbol variabel pada sebelah kanan harus berada pada posisi paling kanan)

Catatan

• Aturan produksi seperti : 

1. ε →Abd 
   bukan aturan produksi yang legal, karena simbol ε tidak boleh berada pada ruas kiri 

• Aturan produksi yang ruas kirinya hanya memuat simbol terminal saja, seperti : 

1. a → bd 
2. ab → bd 
   bukan aturan produksi yang legal, karena ruas kiri juga harus memuat simbol yang bisa diturunkan.