Chomsky Hierarchy terhadap Bahasa / Grammar Komputasi

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.

Apa saja level yang berbeda dalam Chomsky Hierarchy?

1. Regular Grammar (Level/Tipe 3)
   Mesin Automata : Finate State Automata.
   Set paling ketat, mereka menghasilkan bahasa biasa. Mereka harus memiliki satu non-terminal di sisi kiri dan sisi kanan yang terdiri dari satu terminal atau terminal tunggal diikuti oleh satu non-terminal.
   Aturan :
   
   • Simbol sebelah kiri harus berupa simbol variabel.
   • Simbol sebelah kanan maksimal hanya memiliki simbol variabel dan bila ada terletak di paling kanan.
2. Context-Free (Level/Tipe 2)
   Mesin Automata : Push Down Automata.
   Menghasilkan bahasa tanpa konteks, kategori yang sangat menarik bagi praktisi NLP . Di sini semua aturan mengambil bentuk A → β, di mana A adalah simbol non-terminal tunggal dan β adalah string simbol.
   Aturan :
   
   • Simbol sebelah kiri harus simbol variabel.
3. Context-Sensitive (Level/Tipe1)
   Mesin Automata: Linier Bounded Automata.
   Level tertinggi yang dapat diprogram, menghasilkan bahasa sensitif konteks. Mereka memiliki aturan bentuk α A β → α γ β dengan A sebagai non-terminal dan α, β, γ sebagai string terminal dan non-terminal. String α, β boleh kosong, tetapi γ harus tidak kosong.
   Aturan :
   
   • Simbol pada ruas sebelah kiri harus minimal ada sebuah variabel.
   • |a| ≤ |b| artinya ruas sebelah kiri tidak lebih besar dari ruas sebelah kanan.
4. Recursively Enumerable (Level/Tipe 0)
   Mesin Automata : Mesin Turing.
   Terlalu umum dan tidak terbatas untuk mendeskripsikan sintaks dari bahasa pemrograman atau bahasa alami.
   Aturan :
   
   • Simbol ruas sebelah kiri harus minimal ada sebuah simbol variabel.
   • Tidak ada batasan pada aturan produksi.