Teknik Kompilasi Pertemuan 7

HIRARKI CHOMSKY

Pada tahun 1956-1959 Noam Chomsky melakukan penggolongan tingkatan dalam bahasa berdasarkan aturan produksi,yaitu menjadi empat class yang disebut Hirarki Chomsky. Penggolongan tingkatan yang dilakukan oleh Noam Chomsky ada 4 class yaitu:

Tipe 0 / Unrestricted : tidak ada batasan pada aturan produksi

Abc → De

Tipe 1 / Context sensitive : panjang string ruas kiri harus < (lebih kecil) atau = (sama dengan) ruas kanan

Ab → DeF

CD → eF

Tipe 2 / Context Free Grammar : ruas kiri haruslah tepat satu symbol variabel, yaitu simbol non terminal

B → CDeFg

D → BcDe

Tipe 3 / Regular : ruas kanan hanya memiliki maksimal satu symbol non terminal dan diletakkan paling kanan sendiri

A → e

A → efg

A → efgH

C → D

Contoh soal dan pembahasan:

•Grammar G1 dengan Q1 = {S → aB, B → bB, B → b}

Penjelasan :

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.

•Grammar G2 dengan Q2 = {S → Ba, B → bB, B → b}

Penjelasan :

Ruas kiri semua produksinya terdiri dari sebuah VN, maka, G2 kemungkinan adalah tipe CFG atau RG.

Selanjutnya, karena ruas kanannya mengandung string VN VT (Ba), maka, G2 bukan RG. Dengan kata lain G2 adalah CFG.

•Grammar G3 dengan Q3 = {S → aAb, B → aB}

Penjelasan :

Ruas kiri semua produksinya terdiri dari sebuah VN, maka, G3 kemungkinan tipe CFG atau RG.Selanjutnya, karena ruas kanannya mengandung string yang panjangnya lebih dari 2 (yaitu aAb) maka, G3 bukan RG. Dengan kata lain, G3 adalah CFG.

•Grammar G4 dengan Q4 = {S → aA, B → aB, aAb → aBCb}

Penjelasan :

Ruas kirinya mengandung string yang panjangnya lebih dari 1 (yaitu aAb) maka G4 kemungkinan tipe CSG atau UG.Selanjutnya, karena semua ruas kirinya lebih pendek atau sama dengan ruas kanannya maka G4 adalah CSG.

•Grammar G5 dengan Q5 = {aS → aA, B → ab, SAc → bc}

Penjelasan :

Ruas kirinya mengandung string yang panjangnya lebih dari 1 (yaitu aAb) maka G5 kemungkinan tipe CSG atau UG.Selanjutnya, karena semua ruas kirinya yang lebih panjang daripada ruas kanannya (yaitu SAc), maka G5 adalah UG.

sumber:

https://alwihsite.wordpress.com/2017/04/19/hirarki-chomsky-finite-state-otomata-fsa-dan-context-free-grammar-cfg-resume/

http://linslt.blogspot.com/2018/04/contoh-soal-teori-bahasa-dan-otomata.html?m=1