Teknik Kompilasi Pertemuan 6

Contoh 5 soal beserta jawaban "Grammar Chomsky"

1. Sebutkan Langkah-langkah pembentukan bentuk normal Chomsky secara umum ?

Biarkan aturan produksi yang sudah dalam bentuk normal Chomsky Lakukan penggantian aturan produksi yang ruas kanannya memuat simbol terminal dan panjang ruas kanan > 1Lakukan penggantian aturan produksi yang ruas kanannya memuat > 2 simbol variabel Penggantian-penggantian tersebut bisa dilakukan berkali-kali sampai akhirnya semua aturan produksi dalam bentuk normal Chomsky Selama dilakukan penggantian, kemungkinan kita akan memperoleh aturan-aturan produksi baru, dan juga memunculkan variabel baru

2.Aturan produksi yang sudah dalam bentuk normal Chomsky?

A → a

B → b

Dilakukan penggantian aturan produksi yang belum bentuk normal Chomsky (‘=>’ bisa dibaca berubah menjadi):

S → bA => S → P1A

S → aB => S → P2B

A → bAA =>A → P1AA => A → P1P3

A → aS => A → P2S

B → aBB => B → P2BB => B → P2P4

B → bS => B → P1S

Terbentuk aturan produksi dan simbol variabel baru:

P1 → b

P2 → a

P3 → AA

P4 → BB

Hasil akhir aturan produksi dalam bentuk normal Chomsky :

A → a

B → b

S → P1A

S → P2B

A → P1P3

A → P2S

B → P2P4

B → P1S

P1 → b

P2 → a

P3 → AA

P4 → BB

P1 = P, P2 =Q, P3 =R, P4 =T

sehingga aturan produksinya menjadi:

S → PA

S → QB

A → PR

A → QS

A → a

B → QT

B → PS

B → b

P → b

Q → a

R → AA

T → BB

3. Sebutkan klasifikasi Grammar menurut Chomsky!

1. TATA BAHASA (GRAMMAR)

Bahasa merupakan himpunan kalimat (baik terhingga maupun tak terhingga). Bahasa dapat disajikan dengan menyebut kalimatnya satu persatu. Untuk bahasa tak hingga, penyebutan seperti itu tidak mungkin. Oleh karena itu diciptakan cara penyajian yang mendeskripsikan bahasa secara efisien. Cara penyajian tersebut adalah Tata Bahasa atau Grammar.

Sebuah Tata Bahasa (Grammar) didefinisikan sebagai 4 tupel :

G = (Vn, Vt, S, Q)

Vn dan Vt adalah simbol Non Terminal dan Simbol Terminal.

S adalah sebuah elemen anggota Vn yang disebut Simbol Start. Q merupakan himpunan Produksi.

4. Sebutkan salah satu pengelompokan Grammar menurut Chomsky

1. Tipe nol : UnRestricted Grammar (Tata Bahasa Tidak Terbatasi)

Tata Bahasa UnRestricted yang tidak merupakan anggota dari klasifikasi lainnya ditandai dengan aturan produksi yang bagian sebelah kirinya lebih panjang dari bagian sebelah kanan. Aturan produksi yang mengandung simbol hampa (^) pasti merupakan Tata Bahasa UnRestricted dan tidak termasuk klasifikasi lainnya.

5. Jelaskan pengertian chomsky

Chomsky adalah salah satu pemrakarsa teori pemerolehan bahasa yang meyakini bahwa proses pemerolehan bahasa adalah suatu proses mental atau sebuah hirarki penahanan kelas tata bahasa formal. Yang digambarkan oleh Noam Chomsky pada tahun 1956. Hal ini juga dinami Marcel-Paul Schutzenberger, yang memainkan peran penting dalam pengembangan teori bahasa formal. Pada dasranya Chomsky Hierarchy ini memungkinkan kemungkinan bagi pemahaman dan penggunaan model ilmu komputer yang memungkinkan programmer untuk mencapai tujuan linguistik bermakna sistematis.

DAFTAR PUSTAKA

- http://web.if.unila.ac.id/ilmukomputer/cnf-chomsky-normal-form/

- http://chaetiefha.blogspot.com/2014/05/klasifikasi-grammar-menurut-chomsky.html?m=1

- http://andimeapasdkteknikkompilasi.blogspot.com/2018/10/klasifikasi-chomsky-dan-contoh.html?m=1