NEW
Font size
WorksheetsQUiz 10 Teori Bahasa dan Otomata 2021-1-Jadi
Total questions: 10
Worksheet time: 10mins
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
