PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS (Teori Bahasa dan Automata)

PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS

Sebelum kita membahas tentang peneyederhanaan tata bahasa bebas konteks , kita terlebih dahulu harus mengetahui apa tujuannya bukan? Sehingga akan mempermudah kita dalam memahaminya.

Tujuan dari penyederhanaan tata bahasa bebas konteks adalah melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tak perlu atau aturan produksi yang tidak berarti.

Suatu tata bahasa bebas konteks dapat disederhanakan dengan melakukan : 

1. Penghilangan produksi useless (tidak berguna)
2. Penghilangn produksi unit
3. Penghilangan produksi ε  

A.Penghilangan produksi useless

Produksi useless didefinisikan sebagai :

• Produksi yang memuat simbol variabel yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya, produksi ini tidak berguna karena bila diturunkan tidak akan pernah selesai.
• Produksi yang tidak akan pernah di capai dengan penurunan apapun dari simbol awal, sehingga produksi itu redundan (berlebih) 

Contoh menghilangkan produksi useless :

a.)  S → aB | C 

      B → e |Ab
      C → bCb | adF | ab
      F → cFB 

Analisis :

B → | Ab ( A tidak punya penurunan , sehingga harus dihilangkan)

F → cFB ( F tidak ada turunan keterminal , sehingga harus dihilangkan)

C → adF ( Karena F sudah di hilangkan , maka  C → adF harus dihilangkan karena useless)
Hasilnya adalah :
      S → aB | C 

      B → e
      C → bCb | ab

b.)  S → Aa | B

      A → ab | D
      B → b | E
      C → bb
      E → aEa

Analisis : 

A → D (D tidak punya penurunan, jadi D useless harus dihapus)

C → bb ( C tidak berguna , karena tidak dipakai dimanana, ini adalah redundant)

E → aEa (E tidak mempunyai turunan keterminal, dan akan menyebabkan looping maka harus dihapus)

B →E ( Karena E sudah dihapus , maka B→E useless)
Hasilnya adalah :
      S → Aa | B
      A → ab
      B → 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

Keberadaannya membuat tata bahasa memiliki kerumitan yang tak perlu. Penyederhanaan dilakukan dengan melakukan penggantian aturan produksi unit. Kita lakukan penggantian (Penghilangan Produksi Unit) berurutan mulai dari aturan produksi paling dekat menuju terminal- terminal.

Contoh penghilangan produksi unit : 

a.)  S → Aa | B

      B → A | bb

      A → a | bc | B

Analisis : 
Kalau dilihat dari dari teori yang dicetak tebal,
A → B bisa diganti menjadi A → bb.
Sehingga :
A → a | bc | bb
Lalu B → A | bb  bisa diubah menjadi 
B → a | bc | bb
Lalu S → Aa | B pun bisa diubah menjadi
S → Aa | a | bc | bb

Sehingga hasilnya menjadi :
S → Aa | a | bc | bb
B → a | bc | bb
A → a | bc | bb


b.)  S → A | Aa

      A → B
      B → C | b
      C → D | ab
      D → b

Analisis : 
C → D | ab bisa diubah menjadi,
C → b | ab, lalu B → C | b diubah menjadi
B → b | ab , Lalu  A → B diubah menjadi  
A →b | ab , dan yang terakhir  S → A | Aa menjadi  S → b | a | Aa

Sehingga hasilnya menjadi :
S → b | a | Aa
A → ab | b
B → ab | b
C → b | ab 
D → b 

 C. PenghilangProduksi  ε

Produksi ε adalah produksi dalam bentuk :
a → ε
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 penghilang produksi  ε :

a.) S → AB
     A → abB | aCa | ε
     B → bA | BB | ε
     C → ε
Langkah pertama hilangkan  C,
setelah dihilangkan , akan menjadi
S → AB
A → abB | aa | ε
B → bA | BB | ε
Langkah kedua hilangkan B yang mengandung ε,
sehingga menjadi 
S → AB | A
A → abB | aa | ε | ab
B → bA | BB
Langkah ketiga hilangkan A yang mengandung ε,
setelah dihilangkan menjadi,
S → AB | A | B
A → abB | aa | ab
B → bA | BB | b
Ketika sudah tidak ada ε maka sudah selesai.

b.) S → aBCD | bb | A | ε
      A → CDa | ef
      B → b | Af | ε
      C → BbC | ea
      D → ε 
Langkah pertama, hilangkan D, lalu akan menjadi
S → aBC | bb | A | ε
A → Ca | ef
B → b | Af | ε
C → BbC | ea
Langkah kedua, hilangkan B yang mengandung ε,
lalu akan menjadi 
S → aBC | bb | A | ε | aC
A → Ca | ef
B → b | Af
C → BbC | ea | bc
Lalu yang terakhir hilangkan S yang mengandung ε, sehingga menjadi 
S → aBC | bb | A | aC
A → Ca | ef
B → b | Af
C → BbC | ea | bc

Ketika sudah tidak ada ε maka sudah selesai.


Kesimpulan

Dari semua teknik , untuk menyelesaikan suatu penyederhanaan yang kompleks, terdapat alur yang harus dijalani.

Alur penyederhanaan Tata Bahasa : 

Contoh Soal Kompleks : 

S → BACa
B → AC
A → dC | ε
C → D | ε
D → d

Langkah pertama adalah hilangkan semua ε,  langkah 1 hilangkan C → ε, makan akan menjadi

S → BACa | BAa
B → AC | A
A → dC | ε | d
C → D
D → d

selanjutnya hilangkan A → ε, makan akan menjadi

S → BACa | BAa | BCa | Ba
B → AC | A | C | ε
A → dC | d
C → D
D → d

selanjutnya hilangkan  B → ε,maka akan menjadi

S → BACa | BAa | BCa | Ba | ACa | Aa | Ca | a

B → AC | A | C 
A → dC | d
C → D
D → d

Langkah kedua menghilangkan produksi unit

C → D (diubah menjadi C → d )

B → C (diubah menjadi B → d )

B → A (diubah menjadi B → dC | d )

Sehingga menjadi,

S → BACa | BAa | BCa | Ba | ACa | Aa | Ca | a

B → AC | dC | d 
A → dC | d
C → d
D → d

Langkah ketiga adalah penghilangan produksi useless, dalam kasus ini , D → d adalah useless (Redundant) sehingga harus dihapus.

Jadi hasil akhirnya adalah : 

S → BACa | BAa | BCa | Ba | ACa | Aa | Ca | a    
B → AC | dC | d 
A → dC | d
C → d

Berikut adalah video penjelasan materi dari semua teknik.
 

 

sumber : http://nurimansyah-regudukan.blogspot.com/2009/11/penyederhanaan-tata-bahasa-bebas.html