Quiz 8 TEori Bahasa dan Otomata

Penyederhanaan CFG: Untuk melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yg memiliki kerumitan yang tidak perlu atau.........

• aturan produksi yang tidak berarti

• aturan produksi yang berarti

• aturan produksi yang akurat

• aturan produksi yang tidak rumit

• aturan produksi yang tidak sederhana

S→ AB | a

A → a

Aturan S→ AB tidak berarti karena B

• tidak memiliki penurunan

• memiliki penurunan

• tidak bisa diremehkan

• tidak memiliki induk

• tidak seimbang

Aturan Produksi berikut:

nS → A

A → B

B → C

C → D

D → a | A

Memiliki kelemahan yaitu terlalu panjang jalannya padahal berujung pada S → a, D → A juga menyebabkan.....

• kerumitan.

• kemudahan

• kepanjangan

• nilai kosong

• nilai mutlak

Produksi Useless :

Produksi yang memuat simbol variabel yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya, produksi ini tidak berguna karena bila diturunkan:

• tidak akan pernah selesai (masih ada simbol variabel yang tersisa)

• akan selesai ( walaupun masih ada simbol variabel yang tersisa)

• tidak mudahi (karena masih ada simbol variabel yang tersisa)

• mudah untuk diselesaikan (walaupun masih ada simbol variabel yang tersisa)

• pasti akan pernah selesai (walaupun masih ada simbol variabel yang tersisa)

Perhatikan penurunan berikut:

S → aSa | Abd | Bde

A → Ada

B → BBB | a

-Simbol A tidak memiliki penurunan yang menuju terminal, sehingga bisa dihilangkan

-Konsekuensi no 1, aturan produksi S →

• Abd tidak memiliki penurunan

• Abd memiliki penurunan

• Abd tidak memiliki induk

• Abd memiliki kesalahan penulisan

• Abd tidak memiliki proses

Prinsip penyederhanaan adalah: Prinsipnya setiap kali melakukan penyederhanan kita periksa lagi aturan produksi yang tersisa, apakah semua produksi yang useless sudah.........

• dihilangkan.

• diturunkan.

• diproses.

• dikembalikan.

• dimutasi.

S → Sb

S → C

C → D

C → ef

D → dd

Kita lakukan penggantian berturutan mulai dari aturan produksi yang paling dekat menuju ke penurunan terminal2 ( ‘→’ dibaca ‘menjadi’):

C → D => C → dd

S → C => S → dd | ef

Sehingga disederhanakan menjadi :

manakah yang salah?

• S → Sb

• S → dd | ef

• C → dd

• C → ef

• D → ef

Sederhanakan dengan menghilangkan Unit

S → Sb

S → C dd I ef

C→ ef

D→ dd

Hasil penyederhanaanya adalah:

• S → Sb

  S:→ dd I ef

• S → bb

  S:→ dd I ef

• S → Sb

  S:→ dd I ee

• S → Sb

  S:→ bb I ef

• S → Sb

  S:→ ee I ef

Penghilangan Produksi Unit:

Produksi unit adalah produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu simbol variabel, misalnya : A → B,

C → D.

Keberadaan produksi unit membuat tata bahasa memiliki kerumitan yang tidak perlu atau menambah panjang penurunan.

Penyederhanaan ini dilakukan dengan melakukan

• penggantian aturan produksi.

• penghilangan aturan produksi.

• penamabahan aturan produksi.

• penamabah aturan produksi.

• pengurangan aturan produksi.

Untuk penghilangan Produksi Unit berikut:

S → Cba | D

A → bbC

B → Sc | ddd

C → eA | f | C

D → E | SABC

E → gh

Penggantian yang dilakukan :

D → E => D → gh

C → C dihapus

S → D => S → gh | SABC

Sehingga aturan produksi setelah disederhanakan :(manakah yang salah?)

• S → Cba | gh | SABC

• A → bbC

• B → Sc | ddd dan

  C → eA | f

• D → gh | SABC dan

  E → gh

• D → gh | SABC dan

  E → bbC