Sejarah Hirarki Chomsky
Pada tahun 1959,seorang ahli bernama Noam Chomsky melakukan penggolongan tingkatan bahasa menjadi empat,yang disebut dengan hirarki chomsky. Penggolongan tersebut bisa diketahui melalui tabel berikut.
Image Source : http://rahayuunindra.blogspot.co.id/2015/11/hirarki-chomsky-dan-finite-state.html
Dalam hirarki Chomsky ada 4(empat) kelas pengelompokan suatu bahasa, yaitu:
Reguler (Level/Tipe 3)
Mesin Automata : Finate State Automata. DFA dan NFA
Aturan: - Simbol sebelah kiri harus berupa simbol variabel.
- Simbol sebelah kanan maksimal hanya memiliki simbol variabel dan bila ada terletak di paling kanan
Bebas konteks (Level/Tipe 2)
Mesin Automata : Push Down Automata
Aturan :- Simbol sebelah kiri harus simbol variabel
Context Sensitive (Level/Tipe1)
Mesin Automata: Linier Bounded Automata
Aturan: - Simbol pada ruas sebelah kiri harus minimal ada sebuah variabel
- |a| ≤ |b| artinya ruas sebelah kiri tidak lebih besar dari ruas sebelah kanan.
Unrectricted (Level/Tipe 0)
Mesin Automata : Mesin Turing
Aturan: - Simbol ruas sebelah kiri harus minimal ada sebuah simbol variabel
- Tidak ada batasan pada aturan produksi.
Contoh Soal
Grammar G5 dengan Q5= {S→pK,K→kK, K→k}.
Jawab:
Ruas kiri semua produksinya terdiri dari sebuah VN maka G5 kemungkinan tipe CFG atau RG.Selanjutnya karena semua ruas kanannya terdiri dari sebuah VT atau string VT VN maka G5 adalah RG
sumber : http://lerykapressy.blogspot.com/
