TUGAS Materi 5

Latihan Penyederhanaan Tata Bahasa Bebas Konteks

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


Ini adalah penjelasan berbentuk Video




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/

Komentar

Posting Komentar

Postingan populer dari blog ini

TUGAS MATERI 6

Gambar
Latihan Membuat Pohon Penurunan Parsing/Parse Tree Tata Bahasa Bebas kontek Latihan 1 S à  AA A à  AAA | a | bA | Ab Buatlah pohon penurunan dari himpunan produksi di atas untuk membangkitkan string dengan susunan “bbabaaba”. Jawab:   A => AAA      A => bA (agar mendapat string b sebagai lanjutannya sehingga didapat {bb})      A => a (agar mendapat string a sebagai lanjutannya sehingga didapat {bba})      A => bA (agar mendapat string b sebagai lanjutannya sehingga didapat {bbab})      A => a (agar mendapat string a sebagai lanjutannya sehingga didapat {bbaba})      A => a (agar mendapat string a sebagai lanjutannya sehingga didapat {bbabaa}) Pada simpul kanan (S => A) :      A => bA (agar mendapat string b sebagai lanjutannya maka kita dapat {bbabaab})      A => a (agar mendapat string a sebagai lanjutannya maka kita dapat {bbabaaba})      S => bA (agar mendapat string b sebagai awal sehingga didapat {b}) Pohon penurunan untuk s
Baca selengkapnya

Materi 5 Penyederhanaan Tata Bahasa Bebas Konteks

Tujuan :  •  Melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tak perlu atau aturan produksi yang tidak berarti Contoh : S  →  AB | a S  →  a Cara Penyederhanaan: 1. Penghilangan produksi useless ( tidak berguna ) 2. Penghilangan produksi unit 3. Penghilangan produksi e Penghilangan Produksi Useless Di sini produksi useless didefinisikan sebagai : - Produksi yang memuat symbol variabel yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya. - 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 Maka 1) Simbol variabel A tidak memiliki penurunan yang menuju terminal, sehingga bisa dihilangkan 2) Konsekuensi no (1), aturan produksi S → Abd tidak memiliki penurunan Penyederhanaan menjadi: S → aSa | Bde B → BBB | a Contoh : S → Aa | B A → ab | D B → b | E C → bb E → aEa Maka : 1) Aturan
Baca selengkapnya