Teori Bahasa dan Automata : Tata Bahasa Bebas Konteks (Teknik Penyederhanaan)

Bila pada tata bahasa reguler terdapat pembatasana antara ruas kanan dan kirinya pada aturan produksi, maka pada tata bahasa bebas konteks tidak terdapat pembatasan aturan produksi. Pada aturan produksi : α à β batasannya hanyalah ruas kiri (α) adalah sebuah simbol variabel. Pada tata bahasa regular, bagian yang belum terturunkan tersebut selalu terjadi pada suatu ujung, pada tata bahasa bebas konteks bisa terdapat lebih banyak bagian yang belum terturunkan itu, dan bisa terjadi dimana saja. Ketika penurunan itu telah lengkap, semua bagian yang belum terturunkan telah diganti oleh string-string dari himpunan simbol terminal.

Tujuan dari penyerhanaan tata bahasa bebas konteks adalah agar tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tak perlu atau aturan produksi yang tidak berarti.

Teknik-teknik penyederhanaan tata bahasa bebas konteks adalah :

1. Penghilangan produksi useless
2. Penghilangan produksi unit
3. Penghilangan produksi ε

Penghilangan Produksi Useless

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 redudan (berlebih)

Contoh 1 : penghilangan produksi useless

S → aB|C

B → e|Ab

C → bCb|adF|ab

F → cFB

Maka :

1. B → Ab (A tidak punya penurunan)

2. C → adF (F tidak punya penurunan)

3. F → cFB (F tidak punya penurunan ke terminal)

Hasil penyederhanaan useless adalah :

S → aB|C

B → e

C →bCb|ab

Contoh 2 : penghilangan produksi useless

S → Aa|B

A → ab|D

B → b|E

C → bb

E → aEa

Maka :

1. A → D (D tidak punya penurunan)

2. E → aEa (E tidak punya penurunan menuju terminal)

3. B → E (E tidak punya penurunan)

4. C → bb (termasuk redudan)

Hasil penyederhanaan useless adalah :

S → Aa|B

A → ab

B → b

Penghilangan produksi unit

Produksi unit adalah produksi dimana ruas kiri dan kanan aturan produksinya hanya berupa satu simbol variabel misalnya :

A → B, C → D. Keberadaan produksi unit membuat tata bahasa memiliki kerumitan yang tak perlu atau menambah panjang penurunan. Penyederhanaan ini dilakukan dengan melakukan penggantian aturan produksi unit

Contoh 1 : penghilangan produksi unit

S → Aa|B

B → A|bb

A → a|bc|B

Maka :

1. A → a|bc|B => A → a|bc (B tidak memiliki turunan)

2. B → A|bb => B → a|bc|bb

3. S → Aa|B => S → Aa|a|bc|bb

Hasil setelah penyederhanaan :

S → Aa|a|bc|bb

B → a|bc|bb

A → a|bc

Contoh 2 : penghilangan produksi unit

S → A|Aa

A → B

B → C|b

C → D|ab

D → b

Maka :

1. C → D|ab => C → b|ab

2. B → C|b => B → b|ab|b

3. A → B => A → b|ab|b

4. S → A|Aa => S → b|ab|b|Aa

Hasil setelah penyederhanaan :

S → b|ab|b|Aa

A → b|ab|b

B → b|ab|b

C → b|ab

D → b

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.

Contoh 1 : penghilangan produksi ε

S → AB

A → abB|aCa|ε

B → bA|BB|ε

C → ε

Maka : var yang nullable A, B, C

1. C → ε, maka :

A → abB|aCa => A → abB|aa

2. B → ε, maka :

B → bA|BB|ε => B → bA|BB

A → abB|aa => A → abB|aa|ab

S → AB => S → AB|A

3. A → ε, maka :

B → bA|BB => B → bA|BB|b

S → AB|A => S → AB|A|B

Hasil setelah penyederhanaan :

S → AB|A|B

A → abB|aa|ab

B → bA|BB|b

Contoh 2 : penghilangan produksi ε

S → aBCD|bb|A|ε

A → CDa|ef

B → b|Af|ε

C → BbC|ea

D → ε

Maka : var yang nullable S, B, D

1. S → ε, maka :

S → aBCD|bb|A|ε => S → aBCD|bb|A

2. D → ε, maka :

S → aBCD|bb|A => S → aBC|bb|A

A → CDa|ef => A → Ca|ef

3. B → ε, maka :

C → BbC|ea => C → BbC|ea|bC

S → aBC|bb|A => S → aBC|bb|A|aC

Hasil setelah penyederhanaan :

S → aBC|bb|A|aC

A → Ca|ef

B → b|Af

C → BbC|ea|bC

Penyederhanaan dengan penghilangan empty+unit+useless sekaligus

Alur Penyederhanaan Tata bahasa bebas konteks

Contoh :

S → BACa

B → AC

A → dC|ε

C → D|ε

D → d

Maka :

Langkah 1 : penghilangan produksi empty

var yang nullabel adalah A, C

C → ε, maka :

A → dC => A → dC|d

B → AC => B → AC|A

S → BACa => S → BACa|BAa

A → ε, maka :

B → AC|A => B → AC|A|C

S → BACa|BAa => S → BACa|BAa|BCa

Langkah 2 : penghilangan produksi unit

1. C → D => C → d

2. B → AC|A|C => B → AC|dC|d

Langkah 3 : penghilangan produksi useless

D → d (Terdapat redudan)

Hasil penyederhanaan :

S → BACa|BAa|BCa

B → AC|dC|d

A → dC|d

C → d