Quiz 11 Teori Bahasa dan Otomata-2023-1 Penyederhanaan FUngsi

Penghilangan produksi ε dilakukan dengan melakukan penggantian produksi yang memuat variabel yang bisa menuju ........

• produksi ε

• produksi awal

• produksi akhir/terminal

• produksi tengah

• produksi bertingkat

Dalam Prinsip Penghilangan produksi ε. Prinsip penggantiannya bisa dilihat kasus berikut :

S → bcAd

A → ε

Pada kasus di atas A nullable, serta A → ε satu-satunya produksi dari A, maka variabel A bisa ditiadakan, hasil penyederhanaan tata bahasa bebas konteks menjadi :

S → bcd

• S → bcd

• S → BCD

• S → bCD

• S → BCd

• S → ε

Untuk bentuk produksi sebagai berikut:

S → bcAd

A → bd | ε

Pada kasus diatas A nullable, tapi A → ε

bukan satu2nya produksi dari A, maka hasil

penyederhanaan menjadi:

• S → bcAd | bcd

  A → bd

• S → bcAd | bcd

• A → bd

• A → bd | ε

• S → bcAd | bcd

  A → bd | ε

Untuk Produksi:

S → AB

A → abB | aCa | ε

B → bA | BB | ε

C → ε

Variabel yang nullable A, B, C. Dari S → AB, maka S juga

nullable. Kita lakukan penggantian :

A → aCa => A → aa

B → bA => B → bA | b

B → BB => B → BB | B

A → abB => A → abB | ab

S → AB => S → AB | A | B | ε

C → ε, B → ε, A → ε dihapus

Perhatikan : untuk penggantian S → AB kita tetap mempertahankan produksi S → ε, karena S merupakan .....

• simbol awal

• simbol akhir

• simbol terminal

• tidak bisa diproduksi lagi

• terlalu rumit

Perhatikan Bagan Penyederhanaan di Atas, Kota kosong yang berisi tandatangan tersebut berisi.....

• CFG yang sudah

  disederhanakan

• Penghilangan

  Produksi ε

• Penghilangan

  Produksi Unit

• CFG

• Memang Kosong

Lakukan penghilangan aturan produksi unit, useless, dan ε dari tata bahasa bebas konteks berikut :

S → a | aA | B | C

A → aB | ε

B → Aa

C → cCD

D → ddd

Penghilangan Produksi ε :

A → ε dihilangkan, shg :

A → aB

B → Aa | a

S → a | aA | B | C

Penyederhanaannya Menjadi :

Penghilangan Produksi Useless :

1.C tidak memiliki penurunan, shg C → cCD dihilangkan

2.S → cCD dihilangkan

3.Konsekuensi no 2, D → ddd dihilangkan

Sehingga menjadi :

• S → a | aA | Aa

  A → aB

  B → Aa | a

• S → a | aA | B | C

  A → aB

  B → Aa

  C → cCD

  D → ddd

• S → a | aA | B | C

  A → aB

  B → Aa | a

  C → c

  D → dddS → a | aA | B | C

  A → aB

  B → Aa | a

  C → cCD

  D → ddd

• S → a | aA | B | C

  A → aB

  B → Aa | a

• S → a | aA | B | C

  A → aB

Penghilangan Produksi Unit :

S → B => S → Aa | a

S → C => S → cCD

Sehingga menjadi :

S → a | aA | Aa | cCD

A → aB

B → Aa | a

C → cCD

D → ddd

Penghilangan Produksi ε :

A → ε dihilangkan, sehingga :

B → bA => B → b

B → ε dihilangkan, shg :

S → aB => S → aB | a

S → aaB => S → aaB | aa

Sehingga Menjadi :

• S → aB | a | aaB | aa

  B → b

• S → aB | a | aaB | aa

• B → b

• S → aB | a | aaB

  B → b

• S → aB | a

  B → b

Dalam Penghilangan Produksi Unit :

Tidak ada karena semua aturan produksi tidak ada yang ruas kiri dan kanannya mempunyai .......

• sebuah simbol variabel

• dua buah simbol variabel.

• tiga buah simbol variabel.

• empat buah simbol variabel.

• lima buah simbol variabel.

Dalam kasus Penghilangan Produksi Useless :

Karena tidak ada yg redundan dan semua aturan produksinya sudah sederhana, maka hasil dari penghilangan produksi useless =

• hasil dari penghilangan produksi ε

• hasil dari penambahan produksi ε

• hasil dari pengurangan produksi ε

• hasil dari manipulasi produksi ε

• hasil dari pengolahan produksi ε

Perhatikan Gambar di Atas:

Gambar tersebut merupakan bagan untuk:

• Penyederhaan CFG

• Simulasi CFG

• Penambahan CFG

• Pengurangan CFG

• Taha-Tapap CFG