Teori Bahasa Dan Automata - Tata Bahasa Bebas Konteks (Latihan Penyederhanaan)
Assalamualaikum
Wr. Wb.
Pada postingan ini saya akan membagikan sebuah materi penyederhanaan tata bahasa bebas konteks. Tujuan saya membuat postingan ini adalah untuk memenuhi Tugas Materi 5 pada Mata Perkuliahan TEORI BAHASA DAN AUTOMATA.
Disini saya akan membahas latihan dari penyederhanaan tata bahasa bebas konteks baik dengan menggunakan cara penghilangan produksi useless, penghilangan produksi unit, maupun penghilangan produksi empty(ε).
Disini saya akan membahas latihan dari penyederhanaan tata bahasa bebas konteks baik dengan menggunakan cara penghilangan produksi useless, penghilangan produksi unit, maupun penghilangan produksi empty(ε).
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
Proses Penyederhanaan:
1. S
→ aB
2. S
→ C
3. B
→ e
4. B
→ Ab (A tidak punya penurunan)
5. C
→ bCb
6. C
→ adF (F tidak punya penurunan)
7. C
→ ab
8. F
→ cFB (F tidak punya penurunan
ke terminal)
Hasil:
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
Proses Penyederhanaan:
1. S
→ Aa
2. S
→ B
3. A
→ ab
4. A
→ D (D tidak punya penurunan)
5. B
→ b
6. B
→ E (Konsekuensi proses ke-8)
7. C
→ bb (Redundan)
8. E
→ aEa (E tidak punya penurunan ke
terminal)
Hasil:
S → Aa | B
B → ab
B → 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 menghilangkan
Produksi Unit
S → Aa | B
B→ A | bb
A → a | bc | B
Proses Pergantian (Penghilangan Produksi
unit):
1. S
→ Aa
2. S
→ B (diganti menjadi S → a | bb | bc)
3. B
→ A (diganti menjadi B → a | bc)
4. B
→ bb
5. A
→ a
6. A
→ bc
7. A
→ B (diganti menjadi A → bb)
Hasil:
S → Aa | a | bb | bc
B → a | bc | bb
A → a | bc | bb
Soal Latihan 2
Penyederhanaan dengan menghilangkan
Produksi Unit
S → A | Aa
A→ B
B → C | b
C → D | ab
D → b
Proses Penggantian (Penghilangan Produksi
Unit):
1. S
→ A (diganti menjadi S → b)
2. S
→ Aa
3. A
→ B (diganti menjadi A → b | ab)
4. B
→ C (diganti menjadi B → ab | b)
5. B
→ b
6. C
→ D (diganti menjadi C → b)
7. C
→ ab
8. D
→ b
Hasil Penyederhanaan:
S → b | Aa
A → b | ab
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 → ε
Proses Penyederhanaan:
1. S
→ AB (diganti menjadi S → AB | A | B)
2. A
→ abB (diganti menjadi A → abB | ab)
3. A
→ aCa (diganti menjadi A → aa)
4. A
→ ε (nullable, dihapus)
5. B
→ bA (diganti menjadi B → bA | b)
6. B
→ BB (diganti menjadi B → BB | B)
7. B
→ ε (nullable, dihapus)
8. C
→ ε (nullable, dihapus)
Hasil:
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 → ε
Proses Penyederhanaan:
1. S
→ aBCD (diganti menjadi S → aBCD | aBC | aBD | aCD | aa )
2. S
→ bb
3. S
→ A
4. S
→ ε (nullable, dihapus)
5. A
→ cDa (diganti menjadi A → Ca | Da )
6. A
→ ef
7. B
→ b
8. B
→ Af (diganti
menjadi B → Af | f )
9. B
→ ε (nullable, dihapus)
10. C
→ BbC (diganti menjadi C → bc)
11. C
→ ea
12. D
→ ε (nullable, dihapus)
Hasil:
S → aBCD | aBC | aBD | aCD | aa | bb | A
A → Ca | Da | ef
B → b | Af | f
C → 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
Proses
Penyederhanaan:
1. S
→ BACa (konsekuensi proses ke 2, 3,
4, 5, 6)
2. B
→ AC (konsekuensi proses ke-3,
4, 5, 6)
3. A
→ dC (C tidak punya
turunan)
4. A
→ ε (nullable, dihapus)
5. C
→ D (konsekuensi proses ke-7)
6. C
→ ε (nullable, dihapus)
7. D
→ d (redundant)
Hasil:
S → ε
Video Penjelasan:
Video juga bisa ditonton Youtube
Itulah hasil penjelasan saya, mohon maaf apabila terdapat kesalahan dalam proses pengerjaan. Semoga ilmu yang ada di postingan saya dapat bermanfaat bagi kita semua.
Terima Kasih
Wassalamualaikum Wr. Wb.
-----------------------------------------------------------------------------------------------------------------------------------------------Daftar Pustaka:
Materi Persentasi "Penyederhaan Tata Bahasa Bebas Konteks" Dosen pengampu Teori Bahasa Automata: Garno, M.Kom. Fakultas Ilmu Komputer Universitas Singaperbangsa Karawang
https://herilovemetallica.blogspot.com/2009/10/penyederhanaan-tata-bahasa-dalam-teori.html
https://slideplayer.info/slide/3649861/
Komentar
Posting Komentar