Tugas 5 : Latihan Penyederhanaan Tata Bahasa Bebas Konteks

Halo...

Pada kesempatan kali ini saya akan membahas latihan dari tugas 5 tentang penyederhanaan tata bahasa bebas konteks baik dengan menggunakan cara penghilangan produksi useless, penghilangan produksi unit, penghilangan produksi empty(ε), dan latihan kompleks.

Penyederhanaan dengan penghilangan produksi useless

Soal latihan 1

S → aB | C
B → e | Ab
C → bCb | adF | ab
F → cFB

Jawab :

B → Ab (A tidak punya penurunan)
C → adF (F tidak punya penurunan)
F → cFB (F tidak punya penurunan yang menuju simbol terminal)

Jadi, setelah disederhanakan :
S → aB | C
B → e

C → bCb | ab

Soal Latihan 2

S → Aa | B
A → ab | D
B → b | E
C → bb
E → aEa
 

Jawab :

A → D (A tidak punya penurunan)
C → bb (C → bb adalah redudant)

Simbol variabel E tidak memiliki aturan produksi menuju terminal
E → aEa (E tidak punya penurunan ke terminal)

B → E ( E tidak punya penurunan)

Jadi, setelah disederhanakan :

S → Aa | B

A → ab
B → b

Penyederhanaan dengan penghilangan produksi unit

Soal Latihan 1

S → Aa | B

B→ A | bb

A → a | bc | B

Jawab :

Penggantian yang dilakukan

A → B  menjadi  A → bb 

B → A  menjadi  B → a | bc
S → B  menjadi   S → a | bc | bb

Jadi, setelah disederhanakan :

S → Aa | a | bc | bb
B → a | bc | bb

A → a | bc | bb

Soal Latihan 2

S → A | Aa

A→ B

B → C | b

C → D | ab

D → b

Jawab :

Pengganti yang dilakukan

C → D  menjadi  C → b

A → B  menjadi  A → ab | b 

B → C  menjadi  B → b | ab

S → A   menjadi  S → ab | b

Jadi, setelah disederhanakan :

S → b | Aa | ab

A → b | ab

B → ab | b

C → b | ab

D → b

Penyederhanaan dengan penghilangan produksi empty (ε)

Soal Latihan 1

S → AB

A → abB | aCa | ε

B → bA | BB | ε

C → ε

Jawab :

Penghilangan produksi empty (ε)

S → AB   menjadi   S → AB | A | B

A → abB  menjadi  A → abB | ab

A → aCa  menjadi  A → aa

B → bA    menjadi  B → bA | b

B → BB   menjadi   B → BB | B

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

Jadi, setelah disederhanakan :

S → AB | A | B

A → abB | ab | aa

B → bA | b | BB | B

Soal Latihan 2

S → aBCD | bb | A | ε

A → CDa | ef

B → b | Af | ε

C → BbC | ea

D → ε

Jawab :

Penghilangan produksi empty (ε)

Variabel yang nullable: S,B,D

S → ε , B → ε , D → ε dihapus

A → CDa | ef               menjadi  A → Ca | ef

S → aBCD | bb | A | ε  menjadi  S → aBC | bb | A | ε

C → BbC | ea               menjadi  C → BbC | bC| ea

S → aBC | bb | A | ε     menjadi   S → aBC | aC | bb | A | ε

S → aBC | aC | bb | A

Jadi, setelah disederhanakan :

S → aBC | aC | bb | A

A → Ca | ef

B → b | Af

C → BbC | bC | ea

Latihan Kompleks

Lakukan penyederhanaan pada himpunan produksi berikut dengan penghilangan empty + 

unit + useless sekaligus.

S → BACa

B → AC

A → dC | ε

C → D | ε

D → d

Untuk menjawab soal latihan kompleks diatas kita harus mengerjakannya sesuai dengan urutan penyederhanaan tata bahasa bebas konteks. Pertama menghilangkan produksi empty(ε), kemudian menghilangkan produksi unit, dan terakhir menghilangkan produksi useless.

Penghilangan produksi empty(ε):

Jawab :

 Variabel yang nullable: A,C, maka:

A → ε (dihapus)

C → ε (dihapus)

Maka:

S → BACa |BAa | BCa

B → AC | A | C

A → dC | d

C → D 

D → d

Penghilangan produksi unit:

Jawab :

C → D menjadi  C → d

B → A  menjadi  B → dC | d

B → C  menjadi  B → d

Maka:

S → BACa |BAa | BCa

B → AC | dC | d

A → dC | d

C → d 

D → d

Penghilangan produksi useless:

Jawab :

D → d (D → d adalah redudant)

Jadi, hasil akhir penyederhanaannya adalah: 

S → BACa |BAa | BCa

B → AC | dC | d

A → dC | d

C → d

Untuk lebih jelasnya dapat melihat video pembahasan penyederhanaan tata bahasa bebas konteks dibawah ini

Daftar Pustaka : Materi Persentasi "Penyederhaan Tata Bahasa Bebas Konteks" Dosen pengampu Teori Bahasa Automata: Garno, M.Kom. Fakultas Ilmu Komputer Universitas Singaperbangsa Karawang https://docplayer.info/45902166-Penyederhanaan-tata-bahasa-bebas-konteks-kuliah-online-tba-2012-2013.html http://teoribahasa.blogspot.com/2014/01/teori-bahasa-automata.html https://kikifaradilla.wordpress.com/2015/03/20/tata-bahasa-bebas-konteks-teori-bahasa-automata/