PENGHILANGAN
REKURSIF KIRI
Di susun oleh :
1. Frendy Trisno Barus
1211511710
2. Denis Satio 1211511652
3. Muhammad Chairul Ivandi 1111502090
UNIVERSITAS BUDILUHUR
JAKARTA 2015
Penghilangan Rekursif Kiri
Aturan Produksi Rekursif
Aturan Produksi yang rekursif memilki ruas kanan (hasil
produksi) yang memuat simbol variabel pada ruas kiri. Sebuah aturan produksi
dalam bentuk:
A
βA
merupakan aturan produksi yang rekursif kanan
β=(V∪T)* atau
kumpulan simbol variabel dan terminal
Contoh aturan produksi yang rekursif kanan:
S dS
B adB
Produksi dalam bentuk:
A Aβ
Merupakan aturan produksi yang rekursif kiri, contohnya:
S Sd
B Bad
Produksi yang rekursif kanan menyebabkan pohon penurunan
tumbuh ke kanan, sebaliknya Produksi yang rekursif kiri menyebabkan pohon
penurunan tumbuh ke kiri.
Bisa dilihat pohon penurunanpada
gambar 11.1 dari tata bahasa bebas konteks dengan aturan produksi:
S
aAc
A Ab | ε
Dalam banyak penerapan tata bahasa, rekursif kiri tak
diinginkan. Untuk menghindari penurunan yang bisa mengakibatkan loop kita
perlu menghilangkan sifat rekursif kiri dari aturan produksi. Penghilangan
rekursif kiri disini memungkinkan suatu tata bahasa bebas konteks nantinya
diubah ke dalam bentuk normal Greibach.
Tahapan Penghilangan Rekursif Kiri
Langkah-langkah penghilangan rekursif kiri:
} Pisahkan aturan produksi yang
rekursif kiri dan yang tidak, misal:
Aturan
produksi yang rekursif kiri:
A
Aα1 | Aα2 | Aα3 | ....... Aαn
Aturan
produksi yang tidak rekursif kiri (termasuk produksi ε):
A
β1 | β2 | β3 |
........ Βm
Dari
situ kita bisa tentukan α1, α2, .... αn, dan β1, β2, .... βm dari setiap aturan
produksi yang memiliki
simbol ruas kiri yang sama
} Lakukan penggantian aturan produksi
yang rekursif kiri, menjadi sebagai berikut:
1) A β1Z | β2Z | .... βmZ
2) Z α1 | α2 | α3 |
.... αn
3) Z α1Z | α2Z | α3Z | .... αnZ
Penggantian
diatas dilakukan untuk setiap aturan produksi dengan simbol ruas kiri yang
sama. Bisa muncul simbol variabel baru Z1, Z2 dan seterusnya, sesuai banyaknya variabel yang menghasilkan
produksi yang rekursif kiri.
} Hasil akhir berupa aturan produksi
pengganti ditambah dengan aturan produksisemula yang tidak rekursif kiri.
0 Komentar untuk "Materi Teori Bahasa Dan Otomata - PENGHILANGAN REKURSIF KIRI"