HIRARKI CHOMSKY

HIRARKI CHOMSKY

"Assalamualaikum wr.wb Selamat Pagi,Siang,Sore atau malam brothers semua,kali ini saya akan membahas tentang Materi Grammar dan Bahasa pada matakuliah Teori bahasa Otomata. so check this out brothers!!"

 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....

Hirarki Chomsky

Dalam hirarki Chomsky ada 4(empat) kelas pengelompokan suatu bahasa, yaitu:

1.      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

2.      Bebas konteks (Level/Tipe 2)

Mesin Automata : Push Down Automata

Aturan:- Simbol sebelah kiri harus simbol variabel

3.      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.

4.      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 G1 dengan Q1= {S→aB,B→bB, B→b}.
Jawab:
Ruas kiri semua produksinya terdiri dari sebuah VN maka G1 kemungkinan tipe CFG atau RG.Selanjutnya karena semua ruas kanannya terdiri dari sebuah VT atau string VT VN maka G1 adalah RG