Latihan Tata bahasa bebas konteks

Teknik Penyederhanaan Tata Bahasa Bebas Konteks

Teori Bahasa & Automata

NAMA        : RIZKY DARMAWAN
NPM           : 1810631170022
KELAS       : 4B

Sebuah bahasa formal adalah abstraksi terdiri dari himpunan simbol-simbol dan aturan-aturan yang mana simbol-simbol tersebut bisa dikombinasikan kedalam entitas yang disebut kalimat.

Bahasa adalah himpunan string-string dari simbol-simbol untuk suatu alphabet atau rangkaian simbol-simbol yang mempunyai makna.Bahasa Kosong adalah bahasa yang tidak terdiri dari string-string, dinotasikan dengan ->. Bahasa kosong berbeda dengan bahasa yang terdiri dari string kosong {ε}. Melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tidak perlu atau aturan produksi yang tidak berarti.

Cara Penyederhanaan:

1. Penghilangan produksi useless ( tidak berguna ).

2. Penghilangan produksi unit.

3. Penghilangan produksi (ε).

1. Penyederhanaan dengan penghilangan produksi useless

Untuk menjawab soal latihan penyederhanaan dengan penghilangan produksi useless kita harus menghapus aturan produksi yang tidak memiliki penurunan dan juga aturan produksi yang berlebih atau redudan.

Soal Latihan 1

Penyederhanaan dengan penghilangan produksi Useless.

S → aB | C

B → e | Ab

C → bCb | adF | ab

F → cFB

Jawab :

- Analisis :

B → Ab (A tidak punya penurunan)

C → adF (F tidak punya penurunan)

F → cFB (F tidak punya penurunan ke terminal)

- Hasil Penyederhanaan produksi useless :

S → aB | C

B → e

C → bCb | ab

Soal Latihan 2

Penyederhanaan dengan penghilangan produksi Useless

S → Aa | B

A → ab | D

B → b | E

C → bb

E → aEa

Jawab :

- Analisis :

A → D (A tidak punya penurunan)

B → E (F tidak punya penurunan)

C → bb (C → bb adalah redudan)

E → aEa (E tidak punya penurunan ke terminal)

- Hasil Penyederhanaan produksi useless :

S → Aa | B

B → ab

C → b

2. Penyederhanaan dengan penghilangan produksi unit

Untuk menjawab soal latihan penyederhanan dengan penghilangan produksi unit(produksi di mana ruas kiri dan kanan hanya terdapat satu simbol variabel) yaitu dengan cara penggantian produksi unit berurutan mulai dari aturan produksi yang paling dekat ke terminal.

Soal Latihan 1

Penyederhanaan dengan penghilangan produksi unit .

S → Aa | B

B→ A | bb

A → a | bc | B

Jawab :

- Analisis penghilangan produksi unit :

A → B ==> A → bb 

B → A ==> B → a | bc | bb ,

Karena B → bb sudah ada maka cukup ditulis B → a | bc

S → B ==> S → a | bc | bb

- Hasil Penyederhanaan Produksi Unit :

S → Aa | a | bc | bb

B → a | bc | bb

A → a | bc | bb

Soal Latihan 2

Penyederhanaan dengan penghilangan produksi Unit 

S → A | Aa

A→ B

B → C | b

C → D | ab

D → b

Jawab :

- Analisa penghilangan produksi unit :

C → D ==> C → b

B → C ==> B → b | ab , 

Karena B → b sudah ada maka cukup ditulis B → ab

A → B ==> A → ab | b 

S → A ==> S → ab | b

- Hasil Penyederhanaan produksi unit :

S → ab | b | Aa

A → ab | b

B → ab | b

C → b | ab

D → b

3. Penyederhanaan dengan penghilangan produksi empty (ε)

Untuk menjawab soal latihan penyederhanaan dengan penghilangan produksi empty yaitu dengan cara melakukan penggantian produksi yang nullable.

Soal Latihan 1

Penyederhanaan dengan penghilangan produksi Empty (ε)

S → AB

A → abB | aCa | ε

B → bA | BB | ε

C → ε

Jawab :

- Analisa penghilangan produksi empty (ε) :

Variabel yang nullable: A,B,C, maka:

A → ε (dihapus) 

Maka, S → AB | B

A → abB | ab | aa

B → b | BB 

B → ε (dihapus)

Maka, S → AB | A

B → bA | BB | B

A → abB | ab | aa

C → ε (dihapus)

Maka, A → abB | aa

- Hasil Penyederhanaan produksi empty (ε) :

S → AB | A | B

A → abB | ab | aa

B → bA | b | BB | B

Soal Latihan 2

Penyederhanaan dengan penghilangan produksi Empty (ε)

S → aBCD | bb | A | ε

A → CDa | ef

B → b | Af | ε

C → BbC | ea

D → ε

Jawab :

- Analisa penghilangan produksi empty (ε) :

Variabel yang nullable: S,B,D, maka:

S → ε (dihapus)

B → ε (dihapus)

D → ε (dihapus)

- Hasil Penyederhanaan produksi empty (ε) :

S → aBC | aC | bb | A

A → Ca | ef

B → b | Af

C → BbC | bC | ea

4. 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 saya harus megerjakannya sesuai urutan penyederhanaan tata bahasa bebas konteks. Pertama menghilangkan produksi empty(ε), setelah itu menghilangkan produksi unit, dan terakhir menghilangkan produksi useless.

Jawab :

Penghilangan produksi empty (ε) :

- Analisis :

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 :

- Analisis :

C → D ==> C → d

B → A ==> B → dC | d

B → C ==> B → d

- Maka :

S → BACa |BAa | BCa

B → AC | dC | d

A → dC | d

C → d 

D → d

Penghilangan produksi useless:

- Analisis :

D → d (D → d adalah redudan)

Hasil Akhir Penyederhanaan : 

S → BACa |BAa | BCa

B → AC | dC | d

A → dC | d

C → d