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.
Contoh
Penyederhanaan tata bahasa dalam Teori bahasa dan Otomata,berikut adalah
Cara
Penyederhanaan:
1.
Penghilangan produksi useless ( tidak berguna )
2.
Penghilangan produksi unit
3.
Penghilangan produksi ε
Pembahasan
Melakukan
pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan
yang tidak perlu atau aturan produksi yang tidak berarti.
Contoh
1:
S -> AB | a
A -> a
•
Aturan produksi S -> AB tidak berarti karena B tidak memiliki penurunan
Contoh
2 : S->A
A->B
B->C
C->D
D -> a | A
•
Memiliki kelemahan terlalu panjang jalannya padahal berujung pada S -> a,
•
produksi D -> A juga menyebabkan kerumitan.
Cara
Penyederhanaan:
1.
Penghilangan produksi useless ( tidak berguna )
2.
Penghilangan produksi unit
3.
Penghilangan produksi ε
1 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 -> aB | C
B -> e | Ab
C -> bCb | adF | ab
F -> cFB
Maka
:
1)
Simbol variabel F tidak memiliki penurunan yang menuju terminal, sehingga bisa
dihilangkan
2)
Konsekuensi no (3), aturan produksi C -> adF tidak memiliki penurunan
3)
Aturan produksi B -> Ab dimana A tidak memiliki penurunan, sehingga bisa
dihilangkan
maka
produksi yang useless:
B -> Ab
C -> adF
F -> cFB
Penyederhanaan
menjadi:
S -> aB | C
B -> e
C -> bCb | ab
Contoh
selanjutnya
S -> Aa | B
A -> ab | D
B -> b | E
C -> bb
E -> aEa
Maka
:
1)
Aturan produksi A -> D, simbol variabel D tidak memiliki penurunan.
2)
Aturan produksi C -> bb, Penurunan dari simbol S, dengan jalan manapun tidak
akan pernah mencapai C atau disebut redundan
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
Penyederhanaannya
menjadi:
S -> Aa | B
A -> ab
B -> b
2. Penghilangan Produksi Unit
•
Produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu simbol
variabel, misalkan: A -> B, C -> D.
•
Keberadaannya membuat tata bahasa memiliki kerumitan yang tak perlu.
•
Penyederhanaan dilakukan dengan melakukan penggantian aturan produksi unit.
Contoh:
S -> Aa | B
B -> A | bb
A -> a | bc | B
Dilakukan
penggantian berturutan mulai dari aturan produksi yang paling dekat menuju ke
penurunan terminal-terminal (‘=>’ dibaca ‘menjadi’):
A -> B => A -> bb
B -> A => B -> a | bc
S -> B => S -> a | bc | bb
Sehingga
aturan produksi setelah penyederhanaan:
S -> Aa | a | bc | bb
B -> a | bc | bb
A -> a | bc | bb
Contoh
lain:
S -> A | Aa
A -> B
B -> C | b
C -> D | ab
D -> b
Penggantian
yang dilakukan :
C -> D => C -> b
B -> C => B -> b | ab
A -> B => A -> b | ab | b
S -> A => S -> b | ab | b
Sehingga
aturan produksi setelah penyederhanaan:
S -> b | ab | b | Aa
A -> b | ab | b
B -> b | ab | b
C -> b | ab
D -> b
3. Penghilangan Produksi ε
Produksi
ε adalah produksi dalam bentuk
α -> ε
atau
bisa dianggap sebagai produksi kosong ( empty ). Penghilangan produksi ε
dilakukan dengan melakukan penggantian produksi yang memuat variabel yang bisa
menuju produksi ε, atau biasa disebut nullable.
Prinsip
penggantiannya bisa dilihat kasus berikut:
S -> AB
A -> aBCD | aCa | ε
B -> bA | BB | ε
C -> ε
Maka:
A
-> ε, B -> ε, C->ε dapat dihilangkan maka A -> aBCD menjadi
A -> aBD dan A -> aCa menjadi A -> aa didapat hasil penyederhanaan:
S-> AB
A ->aBD | aa
B -> bA | BB
Contoh
lagi, terdapat tata bahasa bebas konteks:
S -> aBCD | bb | A | ε
A -> CDa | ef
B -> b | aF | ε
C -> BbC | ea
D -> ε
Variabel
yang nullable adalah variabel D, B -> ε, S -> ε. Karena penurunan D ->
ε merupakan penurunan satu-satunya dari D, maka kita ganti A -> CDa menjadi
A -> Ca dan S -> aBCD menjadi S -> aBC. Kemudian produksi D -> ε, B
-> ε, S -> ε kita hapus.
Setelah
penyederhanaan menjadi:
S -> aBC | bb | A
A -> Ca | ef
B -> b | aF
C -> BbC | ea
Prakteknya
ketiga penyederhanaan tersebut dilakukan bersama pada suatu tata bahasa bebas
konteks, yang nantinya menyiapkan tata bahasa bebas konteks tersebut untuk
diubah kedalam suatu bentuk normal Chomsky.
Urutan
penghapusan aturan produksi :
1)
Hilangkan produksi ε
2)
Hilangkan produksi unit
3)
Hilangkan produksi useless
Contoh
:
S -> BACa
B -> AC
A -> dC | ε
C -> D | ε
D -> d
Hilangkan
produksi ε, sehingga menjadi:
C -> ε, maka
A -> dC => A => d
B -> AC => B -> A
S -> BACa => S -> BAa, kemudian C -> ε dihapus
A -> ε, maka
B -> AC => B -> A | C
S -> BACa => S -> BAa | Ba, kemudian A -> ε
dihapus
Sehingga hasil penyederhanaan:
S -> BACa | BAa | Ba
B -> AC | A | C
A -> dC | d
C -> D
D -> d
Tidak ada komentar:
Posting Komentar