Penyederhanaan Tata Bahasa dan konteks bebas

Assalamualaikum wr. wb.

Saya Dwiarti Rahma Utami dengan NPM 1810631170174 dari kelas 4C Teknik Informatika FASILKOM UNSIKA.

PENYEDERHANAAN TATA BAHASA DAN KONTEKS BEBAS

Tujuan Penyederhanaan

Melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tak perlu atau aturan produksi yang tidak berarti.

contoh :

S -> AB | a

A -> a

Kelemahannya : aturan produksi AB menjadi tidak berarti karena B tidak memiliki penurunan.

Suatu tata bahasa bebas konteks dapat disederhanakan dengan melakukan cara berikut ini :

1.Penghilangan produksi useless

2.Penghilangan produksi unit

3.Penghilangan produksi E

Penghilangan Produksi Useless

Produksi useless adalah :

• Produksi yang memuat simbol variabel yang tidak memiliki penurunan yang akan

menghasilkan terminal-terminal seluruhnya (masih ada simbol variabel yang tersisa)

• Produksi yang tidak akan pernah dicapai dengan penurunan apapun dari simbol awal sehingga produksi itu redundan (berlebih).

Contoh :

S -> aSa | Abd | Bde

A -> Ada

B -> BBB | a

C -> h

Dapat disimpulkan :

1. Simbol variabel A tidak memiliki penurunan yang menuju terminal jadi bisa dihilangkan.

2. Konsekuensi dari no (1), aturan S -> Abd tidak memiliki penurunan

3. C -> h adalah Redundan

 Maka tata bahasa bebas konteks setelah disederhanakan menjadi :

S -> aSa | Bde

B -> BBB | a

Contoh Penghilangan Useless

S -> aB I C

A -> bcD I dAC

B -> e I Ab

C -> bCb I adF I ab

F -> cFB

Useless :

1. A -> bcD (D tidak punya penurunan)

2. A -> dAC (A tidak punya penurunan ke terminal)

3. B -> Ab ( A tidak punya penurunan)

4. F -> cFB (F tidak punya penurunan ke terminal)

5. C -> adF (F tidak punya penuruanan)

Penghilangan Produksi Unit

Produksi unit adalah produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu simbol variabel, misalkan A -> B, C -> D

Contoh :

S -> Sb

S -> C

C -> D

C -> ef

D -> dd

Penghilangan Produksi E

 Produksi E adalah produksi dalam bentuk αα -> εε atau bisa dianggap sebagai produksi kosong.

Penghilangan produksi εε dilakukan dengan penggantian produksi yang memuat variabel yang bisa menuju produksi εε atau biasa disebut nullable.

Contoh :

S -> bcAd

A -> εε

Pada kasus diatas A nullable, maka variabel A bisa ditiadakan.

Hasil penyederhanaan :

S -> bcd

Berikut contoh soal dan jawaban mengenai materi ini :

1.       Penyederhanaan dengan penghilangan produksi Useless

S -> aB | C

B -> e |Ab

C -> bCb | adF | ab

F -> cFB

Jawab :

S  -> aB |C

B  -> e

C  -> bCd | aB

2. Penyederhanaan dengan penghilangan produksi Useless

S -> Aa | B

A -> ab | D

B -> b | E

C -> bb

E -> aEa

Jawab :

S  -> Aa | B

A  -> ab

B  -> b

3.       Penyederhanaan dengan penghilangan produksi Unit

S -> Aa | B

B -> A | bb

A -> a | bc | B

Jawab :

S  -> B menjadi a|bb|bC

B  -> A menjadi a|bc

A  -> B menjadi bb

Hasil,

S  -> Aa|a|bb|bc

B  -> a |bc|bb

A  -> a|bc|bb

4.       Penyederhanaan dengan penghilangan produksi Unit

S -> A | Aa

A -> B

B -> C | b

C -> D | ab

D -> b

Jawab :

S  ->  A menjadi b

A  -> B menjadi b|ab

B  -> C menjadi ab|b

C  -> D menjadi b

Hasil,

S  -> B |Aa

A  -> B |AB

B  -> ab |b|b

C  -> b |ab

D  -> b|b

5.       Penyederhanaan dengan penghilangan produksi Empty (ε)

S -> AB

A -> abB | aCa | ε

B -> bA | BB | ε

C -> ε

Jawab :

S  -> AB | A|B

A   -> abB|ab|aa

B  -> bA|b|BB|B

6.       Penyederhanaan dengan penghilangan produksi Empty (ε)

S -> aBCD | bb | A | ε

A -> CDa | ef

B -> b | Af | ε

C -> BbC | ea

D -> ε

Jawab :

A  -> CDA |eA

B  -> b |Af

C  -> Bbc|bC|ea

7.       Lakukan penyederhanaan pada himpunan produksi berikut dengan penghilangan empty+unit+useless sekaligus.

S -> BACa

B -> AC

A ->dC | ε

C -> D | ε

D -> d

Jawab :

Hasil penyederhanaan unit

S  -> BACA |Baa|BCa|Ba

A  -> AC|dC|d

B  -> dC|d

C  -> d

D  -> d

Hasil penyederhanaan useless

S  -> BACa|BAa|BCa|Bc

B  -> Ac|dc|d

A  -> dc|d

C ->d

Penjelasan soal dan jawaban dalam bentuk video :

Terima kasih.
wassalamualaikum wr. wb.


source materi :
Materi PPT dosen Teori Bahasa dan Automata, Pak Garno (Dosen Unsika).