Pengertian
Bahasa Bebas Konteks
(CRF) adalah sebuah tata bahasa dimana tidak terdapat pembatasan pada hasil
produksinya. Contoh pada aturan produksi : a → b
Batasan hanyalah ruas
kri (a) adalah sebuah symbol variable. Sedangkan contoh aturan produksi yang
termasuk CFG adalah sebagai berikut:
B → cDeFg
D → BcDe
Tata bahasa bebas
konteks (CFG) adalah tata bahasa yang mempunyaitujuan sama seperti halnya tata
bahasa regular yaitu merupakan suatu cara untuk menujukan bagaimana
menghasilkan suatu untai-untai dalam suatu bahasa.
Penyederhanaan
Tata Bahasa Bebas Konteks (CFG)
Penyederhanaan
tata bahasa bebas konteks ini memiliki tujuan agar tidak menghasilkan pohon
penurunan yang memiliki kerumita yang tidak diperlukan atau menghilangkan atau
produksi yang tidak berarti.
Langkah-langkah
penyederhanaan dari tata bahasa bebeas konteks ini adalah dengan cara:
1. Menghilangkan
Produksi yang useless (tidak berguna)
2. Menghilangkan
produk unit
3. Menghilangkan
produk ε
Apa yang dimaksud dengan produksi uselees, produk
unit dan produk ε ? dan bagaimana cara menghilangkanya :
1. Menghilangkan Produksi Uselees
Produksi Uselees didefinisikan sebagai berikut :
- Produksi yang memuat symbol variable yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya
- Produksi yang tidak akan pernah dicapai dengan penurunan apapun dari symbol awal, sehingga produk itu redudan.
Contoh:
Terdapat aturan
produksi sebagai berikut :
S
→ aBD
B
→ cD | Ab
D
→ ef
A
→ Ed
F
→ dc
Analisa :
1) Pada
aturan produksi A → Ed , E tidak memiliki penurunan. Sehingga dapat dihilangkan
2) Aturan
produksi F → dc, redudan. Sehingga aturan produksi tersebut dapat dihilangkan
3) Aturan
produksi B → Ab, A tidak memiliki penurunan. Sehingga didapat penyederhanaan.
Maka hasil akhirnya:
S →
aBD
B →
cD
D →
ef
Kesimpulannya adalah bahwa produk usselees yang
dihilangkan adalah:
A →
Ed
F →
dc
B → Ab
Produk Unit adalah
produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu simbol variabel.
Contoh A → B, atau C → D
Keberadaan produksi unit ini membuat tata bahasa
memiliki kerumitan yang tak perlu. Untuk menyederhanakan produksi unit,
dilakukan penggantian aturan produksi unit tersebut.
Contoh
:
Diberikan aturan produksi sebagai berikut :
S →
A
S →
Aa
A → B
B → C
B → b
C → D
C → ab
D → b
Lakukan penggantian berurutan mulai dari aturan
produksi yang paling dekat menuju kw penurunan terminal-terminal (“=>”
dibaca”menjadi”)
C →
D => C → b
B →
C => B → b | ab, karena B → b sudah ada maka cukup ditulis B → ab
A →
B => A → ab | b
S →
A => S → ab | b
Sehingga aturan produksi yang telah disederhanakan
dengan menghilangkan produksi unit adalah sebagai berikut :
S → ab | b
S → Aa
A → ab | b
B → ab
B → b
C → b
C → ab
D → b
3. Menghilangkan
Produksi ε
Produksi ε adalah
produksi dalam bentuk α → ε atau bias dianggap sebagai produksi kosong (empty)
Penghilangan produksi ε dilakukan dengan melakukan penggantian
produksi yang memuat variable yang bias menuju produksi ε, atau disebut juga Nullable
Contoh
:
Terdapat tata bahasa bebas konteks sebagai berikut :
S → aB | Cd
A → d
C → ε
Variabel yang nullable
adalah variable C, karena penurunan C → ε merupakan penurunan satu-satunya
dari C, maka kita ganti S → Cd menjadi S → d, kemudian produksi C → ε kita
hapus.
Maka hasil penyederhanaannya adalah :
S → aB | d
A → d
