Contoh Penyederhanaan tata bahasa dalam Teori bahasa dan Otomata

Contoh Penyederhanaan tata bahasa dalam Teori bahasa dan Otomata

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 ε

Kata kunci : input, output, state, useless.

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:
4. Penghilangan produksi useless ( tidak berguna )
5. Penghilangan produksi unit
6. 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 -> 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 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
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 v Aa | B
A -> ab
B -> b
Contoh :
S -> aAb | cEB
A -> dBE | eeC
B -> ff
C -> ae
D -> h
Analisa :
1) Aturan produksi S -> cEB, A -> dBE dapat dihilangkan ( E tidak memiliki penurunan)
2) Aturan produksi D -> h, redundan
Sisa aturan produksi
S -> aAb
A -> eeC
B -> ff
C -> ae
Analisis lagi
B -> ff juga redundan,
Hasil penyederhanaan menjadi:
S -> aAb
A -> eeC
C -> ae
Contoh lain lagi :
S -> aB
A -> bcD | dAC
B -> e | Ab
C -> bCb | adF | ab
F -> cFB
Analisis
1) Aturan produksi A -> bcD, variabel D tidak memiliki penurunan
2) Konsekuensi no (1), simbol variabel A tidak memiliki penurunan yang menuju terminal (tinggal A -> dAC)
3) Konsekuensi no (2), B -> Ab tidak memiliki penurunan
4) Simbol variabel F ti
dak memiliki penurunan yang menuju terminal
5) Konsekuensi no (4), C -> adF tidak memiliki penurunan
Setelah disederhanakan menjadi:
S -> aB
B -> e
C -> bCb | ab
Contoh lain lagi :
S -> aBD
B -> cD | Ab
D -> ef
A -> Ed
F -> dc
Analisa
1) Aturan produksi A -> Ed, E tidak memiliki penurunan
2) Aturan produksi F -> dc, redundan
Sisa aturan produksi:
S -> aBD
B -> cD | Ab
D -> ef
Analisa lagi
B -> Ab, A tidak memiliki penurunan.
Hasil penyederhanaan:
S -> aBD
B ->cD
D -> ef
Cont
oh lagi:
S -> Abc | ab
A -> AAA | ε
Aturan produksi setelah disederhanakan:
S -> Abc | ab
A -> AAA | ε
Ingat A -> ε juga harus diperhitungkan
PRINSIP :
Setiap kali melakukan penyederhanaan diperiksa lagi aturan produksi yang tersisa, apakah semua produksi yang useless sudah hilang.

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 -> Sb
S -> C
C -> D
C -> ef
D -> dd
Dilakukan penggantian berturutan mulai dari aturan produksi yang paling dekat menuju ke penurunan terminal-terminal (‘=>’ dibaca ‘menjadi’):
• C -> D => C -> dd
• S -> C => S -> dd | ef
Sehingga aturan produksi setelah penyederhanaan:
S -> Sb
S -> dd | ef
C -> dd | ef
Contoh lain:
S -> A
S -> Aa
A -> B
B -> C
B -> b
C -> D
C ->ab
D -> b
Penggantian yang dilakukan :
• C -> D => C -> b
• B -> C => B -> b | ab, karena B -> b sudah ada, maka cukup dituliskan B -> ab
• A -> B => A -> ab | b
• S -> A => ab | b
Sehingga aturan produksi setelah penyederhanaan:
S -> ab | b
S -> Aa
A -> ab | b
B ->ab
B -> b
C -> b
C -> ab
D -> b
Contoh lagi:
S -> Cba | D
A -> bbC
B -> Sc | ddd
C -> eAn | f | C
Penggantian yang dilakukan:
• D -> E menjadi D -> gh
• C -> C , kita hapus
• S -> D menjadi S -> gh | SABC
Sehingga aturan produksi setelah penyederhanaan:
S -> Cba | gh | SABC
A -> bbC
B -> Sc | ddd
C -> eA | f
D -> gh | SABC
E -> gh

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 -> bcAd
A -> ε
A nullable serta A -> ε satu-satunya produksi dari A, maka variabel A bisa ditiadakan, hasil penyederhanaan tata bahasa bebas konteks menjadi:
S -> bcd
Tetapi bila kasusnya:
S -> bcAd
A -> bd | ε
A nullable, tapi A -> ε bukan satu-satunya produksi dari A, maka hasil penyederhanaan:
S -> bcAd | bcd
A -> bd
Contoh lagi, terdapat tata bahasa bebas konteks:
S -> Ab | Cd
A -> d
C -> ε
Variabel yang nullable adalah variabel C. Karena penurunan C -> ε merupakan penurunan satu-satunya dari C, maka kita ganti S -> Cd menjadi S -> d. Kemudian produksi C -> ε kita hapus.
Setelah penyederhanaan menjadi:
S -> Ab | d
A -> d
Contoh lain lagi:
S -> dA | Bd
A -> bc
A -> ε
B -> c
Variabel yang nullable adalah variabel A. A -> ε bukan penurunan satu-satunya dari A ( terdapat A -> bc ), maka kita ganti S -> dA menjadi S -> dA | d.A -> ε kita hapus.
Setelah penyederhanaan :
S -> dA | d | Bd
A -> bc
B -> c
Contoh tata bahasa bebas konteks:
S -> AaCD
A -> CD | AB
B -> b | ε
C -> d | ε
D -> ε
Variabel yang nullable adalah variabel B, C, D. Kemudian dari A -> CD, maka variabel A juga nullable ( A -> ε ). Karena D hanya memilki penurunan D -> ε, maka kita sederhanakan dulu:
• S -> AaCD => S -> AaC
• A -> CD => A -> C
• D -> ε kita hapus

Selanjutnya kita lihat variabel B dan C memiliki penurunan ε, meskipun bukan satu-satunya penurunan, maka dilakukan penggantian:
• A -> AB => A -> AB | A | B
• S -> AaC => S -> AaC | aC | Aa | a
• B -> ε dan C -> ε kita hapus
Setelah penyederhanaan:
S -> AaC | aC | Aa | a
A -> C | AB | A | B
B -> b
C -> ε
Variabel yang nullable adalah A, B, C. Dari S -> AB, maka S juga nullable. Kita lakukan penggantian:

• A -> aCa => A -> aa
• B -> bA => B -> bA | b
• B -> BB => B v BB | B
• A -> abB => A -> abB | ab
• S -> AB => S -> AB | A | B | ε
• C -> ε, B -> ε, A -> ε dihapus
*Perhatikan untuk penggantian S -> AB kita tetap mempertahankan S -> ε, karena S merupakan simbol awal. Ini merupakan satu-satunya perkecualian produksi ε yang tidak dihapus, yaitu produksi ε yang dihasilkan oleh simbol awal.
Hasil akhir dari penyederhanaan:
S -> AB | A | B | ε
A -> abB | ab | aa
B -> bA | b | BB | B
Contoh tata bahasa bebas konteks:
S -> aAb
A -> aAb | ε
Hasil penyederhanaan:
S -> aAb | ab
A -> aAb | ab
Contoh tata bahasa bebas konteks:
S -> ABaC
A -> BC
B -> b | ε
C -> D | ε
D -> d
Hasil penyederhanaan:
S -> ABaC | BaC | AaC | ABa | aC | Aa | Ba | a
A -> B | C | BC
B -> b
C -> D
D -> d
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 -> AA | C | bd
A -> Bb | ε
B -> AB | d
C -> de
Hilangkan produksi ε, sehingga menjadi:
S -> A | AA | C | bd
A -> Bb
B -> B | AB | d
C -> de
Selanjutnya penghilangan produksi unit menjadi:
S -> Bb | AA | de | bd
A -> Bb
B -> AB | d
C -> de
Penghilangan produksi unit bisa menghasilkan produksi useless.
Terakhir dilakukan penghilangan produksi useless:
S -> Bb | AA | de | bd
A -> Bb
B -> AB | d
Hasil akhir aturan produksi tidak lagi memiliki produksi ε, produksi unit, maupun produksi useless.
Bb | AA | de | bd
A -> Bb
B -> AB | d
Hasil akhir aturan produksi tidak lagi memiliki produksi ε, produksi unit, maupun produksi useless.