Hirarki Chomsky

 "Hirarki Chomsky"

Apa itu Chomsky Hierarchy?

Hirarki Chomsky merupakan tata Bahasa (Grammar) atau yang bisa didefinisikan secara formal sebagai kumpulan dari himpunan - himpunan variable, simbol-simbol terminal, simbol awal, yang dibatasi oleh aturan - aturan produksi. Pada tahun 1959 seorang ahli bernama Noam Chomsky melakukan pengelompokkan tingkatan bahasa menjadi empat level, yang akan dibahas di bawah ini.

1. Regular Grammar (Level/Tipe 3).
   Aturan :
   
   • Simbol sebelah kiri harus berupa simbol variabel.
   • Simbol sebelah kanan maksimal hanya memiliki simbol variabel dan bila ada terletak di paling kanan.
   • Misal : 
   • A → e (diterima)
   • A → fgh (diterima)
   • A → eH (diterima)
   • C → D (diterima)
   • A → Bc (ditolak)
2. Context-Free (Level/Tipe 2)
   Aturan :
   
   • Simbol sebelah kiri harus simbol variabel.
   • Misal : 
   • B → CDeFG (diterima)
   • D → BcDe (diterima)
   • a → b (ditolak)
3. Context-Sensitive (Level/Tipe1)
   
   Aturan :
   
   • Simbol pada ruas sebelah kiri harus minimal ada sebuah variabel.
   • |a| ≤ |b| artinya ruas sebelah kiri tidak lebih besar dari ruas sebelah kanan.
   • Misal : 
   • Ab → DeF (diterima)
   • CD → eF (diterima)
   • S → ε (diterima)
   • ABC → DE (ditolak)
4. Unrestricted (Level/Tipe 0)
   Aturan :
   
   • Simbol ruas sebelah kiri harus minimal ada sebuah simbol variabel.
   • Tidak ada batasan pada aturan produksi.
   • Misal : 
   • Abc → De (diterima)
   • ABC → b (diterima)
   • abc → GHI (ditolak)

Disini dapat diambil kesimpulan bahwa Bahasa tipe 3 sudah termasuk bahasa tipe 2,1, dan 0. Bahasa tipe 2 sudah termasuk bahasa tipe 1, dan 0. Juga bahasa tipe 1 pasti termasuk tipe 0.