PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS
Halo...
Dalam artikel kali ini saya akan menjelaskan tentang penyederhanaan tata bahasa bebas konteks. Apa itu bahasa bebas konteks ? Apa itu tata bahasa bebas konteks ? Bagaimana penyederhanaan tata bahasa bebas konteks ?
Mari kita bahas dibawah ini
Pengertian :
Dalam artikel kali ini saya akan menjelaskan tentang penyederhanaan tata bahasa bebas konteks. Apa itu bahasa bebas konteks ? Apa itu tata bahasa bebas konteks ? Bagaimana penyederhanaan tata bahasa bebas konteks ?
Mari kita bahas dibawah ini
Pengertian :
Bahasa Bebas Konteks (CRF) adalah sebuah tata bahasa dimana tidak terdapat pembatasan pada hasil produksinya. Contoh pada aturan produksi : a → b
Tata bahasa bebas konteks (CFG) adalah tata bahasa yang mempunyai tujuan sama seperti halnya tata bahasa regular yaitu merupakan suatu cara untuk menujukan bagaimana menghasilkan suatu untai-untai dalam suatu bahasa
Tujuan :
• Melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tak perlu atau aturan produksi yang tidak berarti
• 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
Kelemahannya : aturan produksi AB menjadi tidak berarti karena B tidak memiliki penurunan.
Ada 3 bentuk penyederhanaan :
1. Penghilangan produksi useless
2. Penghilangan produksi unit
3. Penghilangan produksi ε
Penghilangan
Produksi Useless
Definisi
Penghilangan 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
B → BBB | a
C → h
Dapat
disimpulkan :
1.
Simbol variabel A tidak memiliki penurunan yang menuju terminal, sehingga
bisa dihilangkan.
2.
Konsekuensi no (1), aturan produksi S → Abd tidak memiliki penurunan.
3. C → h adalah redundan
Setelah penyederhanaan
menjadi :
S → aSa
| Bde
B → BBB
| a
Contoh
:
S → Aa
| B
A → ab
| D
B → b |
EC → bbE → aEa
Maka :
1. Aturan produksi A → D, simbol variabel D tidak memiliki penurunan.
2. Aturan produksi C → bb, penurunan dari simbol dengan jalan manapun tidak akan pernah mencapai C.
3. Simbol variabel E tidak memiliki aturan produksi yang menuju terminal.
4. Konsekuensi no (3) aturan produksi B → E, simbol variabel E tidak memiliki penurunan.
maka produksi yang useless:
A → D
C → bb
E → aEa
B → E
Penyederhanaan menjadi :
S → Aa | B
A → ab
B → b
Penghilangan Produksi Unit
Definisi 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
Melakukan penggantian berurutan mulai dari aturan produksi yang paling terdekat menuju terminal - terminal:
C → D menjadi C → dd
S → C menjadi S → dd | ef
C → D menjadi C → dd
S → C menjadi S → dd | ef
Sehingga Aturan Produksi setelah penyederhanaan :
S → Sb
S → dd | ef
C → dd
C → ef
D → dd
Penghilangan Produksi ε
Definisi Penghilangan Produksi ε
• Produksi ε adalah produksi dalam bentuk α → ε atau biasa dianggap sebagai produksi kosong(empty)
• Penghilangan produksi ε dilakukan dengan melakukan penggantian produksi yang memuat variabel yang bisa menuju produksi ε atau biasa disebut nullable.
Contoh :
S → aB | Cd
A → d
C → ε
*pada kasus diatas C nullable, maka variabel C bisa ditiadakan. Penurunan C → ε merupakan penurunan satu - satunya dari C, maka S → Cd menjadi S → d. Produksi C → ε bisa dihapus.
Hasil Penyederhanaan :
S → aB | d
A → d
Gabungan Useless, Unit, dan ε
Ketiga penyederhanaan ini dilakukan secara bersamaan pada suatu tata bahasa konteks, yang nantinya tata bahasa konteks ini diubah ke dalam bentuk normal Chomsky (CNF).
Urutannya sebagai berikut :
1. Hilangkan produksi ε
2. Hilangkan produksi unit
3. Hilangkan produksi useless
Contoh :
Hilangkan produksi useless, unit, dan empty dari tata bahasa konteks berikut :
S → a | aA | B | C
A → aB | ε
C → cCD
D → ddd
Jawab :
1. Penghilangan produksi ε
2. Penghilangan produksi unit
3. Penghilangan produksi useless
Demikian artikel saya kali ini semoga bermanfaat bagi pembaca dan dapat memahami tentang penyederhanaan tata bahasa bebas konteks dengan cara penghilangan produksi useless, penghilangan produksi unit, dan penghilangan produksi empty(ε).
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/
Comments
Post a Comment