1. MENGENAL OTOMATA
1.1. Definisi Otomata
Otomata adalah mesin
abstrak yang dapat mengenali (recognize),
menerima (accept), atau membangkitkan
(generate) sebuah kalimat dalam
bahasa tertentu.
Sedangkan
arti Otomata menurut American Heritage Dictionary:
1.
a robot.
2.
one that behaves in an automatic or mechanical fashion.
Sementara
dalam dunia matematika, Otomata berkaitan dengan teori mesin abstrak, yaitu
mesin sekuensial yang menerima input, dan mengeluarkan output, dalam bentuk
diskrit. Contoh :
♦ Mesin Jaja / vending machine.
♦ Kunci kombinasi.
♦ Parser/compiler.
1.2. Pengguna Pertama Istilah Otomata
Istilah Otomata
pertama kali tercantum dalam makalah yang berjudul “The Logical and General
Theory of Automata”. Makalah ini ditulis oleh John Von Neumann dari The Institute for Advanced Study dan
disajikan di Hixon Simposium pada tanggal 20 September 1948 di Pasadena,
Kalifornia, Amerika Serikat.
1.3. Buku
Otomata Pertama
Sebagai
kelanjutan dari makalah tersebut, John Von Neumann menulis buku yang berjudul
“Theory of Self-Reproducing Automata”. Buku ini diterbitkan oleh University of
Illinois Press pada tahun 1966.
1.4. Dasar-Dasar
Otomata
Secara garis
besar, otomata mempunyai beberapa dasar, yaitu :
• Simbol adalah sebuah entitas abstrak (seperti halnya pengertian titik dalam
geometri). Sebuah huruf atau sebuah angka adalah contoh simbol.
• String adalah deretan terbatas (finite)
simbol-simbol. Sebagai contoh, jika a, b, dan c adalah tiga buah simbol maka abcb
adalah sebuah string yang dibangun dari
ketiga simbol tersebut.
• Jika w adalah sebuah string maka panjang string dinyatakan sebagai |w| dan
didefinisikan sebagai cacahan (banyaknya) simbol yang menyusun string tersebut.
Sebagai contoh, jika w = abcb maka |w| = 4.
• String hampa adalah sebuah string dengan nol buah simbol. String
hampa dinyatakan dengan simbol ε (atau
^) sehingga |ε| = 0. String hampa dapat dipandang sebagai simbol hampa karena
keduanya tersusun dari nol buah simbol.
• Alfabet adalah hinpunan hingga (finite set) simbol-simbol.
Operasi Dasar String
Diberikan
dua string : x = abc, dan y = 123
·
Prefik string w adalah string yang dihasilkan dari
string w dengan menghilangkan nol atau lebih simbol-simbol paling
belakang dari string w tersebut.
Contoh : abc, ab,
a, dan e adalah semua
Prefix(x)
·
ProperPrefix string w adalah
string yang dihasilkan dari string w
dengan menghilangkan satu atau lebih
simbol-simbol paling belakang dari string w
tersebut.
Contoh : ab, a,
dan e adalah semua ProperPrefix(x)
·
Postfix (atau Sufix) string w
adalah string yang dihasilkan dari string w
dengan menghilangkan nol atau lebih
simbol-simbol paling depan dari string w
tersebut.
Contoh : abc, bc,
c, dan e adalah semua
Postfix(x)
·
ProperPostfix (atau PoperSufix) string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau
lebih simbol-simbol paling depan dari string w tersebut.
Contoh : bc, c,
dan e adalah semua ProperPostfix(x)
·
Head string w adalah simbol paling depan dari string w.
Contoh
: a adalah Head(x)
·
Tail string w adalah string yang dihasilkan dari string w dengan menghilangkan simbol paling depan dari string w tersebut.
Contoh : bc
adalah Tail(x)
·
Substring string w adalah string yang dihasilkan dari
string w dengan menghilangkan nol atau lebih simbol-simbol paling
depan dan/atau simbol-simbol paling belakang dari string w tersebut.
Contoh : abc,
ab, bc, a, b,
c, dan e
adalah semua Substring(x)
·
ProperSubstring string w adalah string yang dihasilkan dari
string w dengan menghilangkan satu atau lebih simbol-simbol paling
depan dan/atau simbol-simbol paling belakang dari string w tersebut.
Contoh : ab,
bc, a, b, c, dan e
adalah semua Substring(x)
·
Subsequence string w adalah string yang dihasilkan dari
string w dengan menghilangkan nol atau lebih simbol-simbol dari string
w tersebut.
Contoh : abc, ab, bc,
ac, a, b, c, dan e
adalah semua Subsequence(x)
·
ProperSubsequence string w adalah string yang dihasilkan dari
string w dengan menghilangkan satu atau lebih simbol-simbol dari
string w tersebut.
Contoh : ab,
bc, ac, a, b,
c, dan e
adalah semua Subsequence(x)
·
Concatenation adalah penyambungan
dua buah string. Operator concatenation adalah concate atau tanpa lambang apapun.
Contoh : concate(xy)
= xy = abc123
·
Alternation adalah pilihan satu di antara dua buah string. Operator
alternation adalah alternate atau ½.
Contoh :
alternate(xy) = x½y
=
abc atau 123
·
Kleene Closure : x* = e½x½xx½xxx½… = e½x½x
½x
½…
·
Positive Closure : x
= x½xx½xxx½… = x½x
½x
½…
Beberapa Sifat Operasi
·
Tidak selalu berlaku : x = Prefix(x)Postfix(x).
·
Selalu berlaku : x = Head(x)Tail(x).
·
Tidak selalu berlaku : Prefix(x) = Postfix(x) atau Prefix(x) ¹
Postfix(x).
·
Selalu berlaku : ProperPrefix(x)
¹ ProperPostfix(x).
·
Selalu berlaku : Head(x) ¹ Tail(x).
·
Setiap Prefix(x), ProperPrefix(x), Postfix(x),
ProperPostfix(x), Head(x), dan Tail(x) adalah Substring(x),
tetapi tidak sebaliknya.
·
Setiap Substring(x) adalah Subsequence(x), tetapi tidak sebaliknya.
·
Dua sifat aljabar concatenation :
¨
Operasi concatenation bersifat
asosiatif : x(yz) = (xy)z.
¨
Elemen identitas operasi
concatenation adalah e : ex = xe = x.
·
Tiga sifat aljabar alternation :
¨
Operasi alternation bersifat
komutatif : x½y
= y½x.
¨
Operasi alternation bersifat asosiatif : x½(y½z) = (x½y)½z.
¨
Elemen identitas operasi
alternation adalah dirinya sendiri : x½x
= x.
·
Sifat distributif concatenation
terhadap alternation : x (y½z) = xy½xz.
·
Beberapa kesamaan :
¨
Kesamaan ke-1 : (x*)* = x*.
¨
Kesamaan ke-2 : e½x
= x
½e = x*.
¨
Kesamaan ke-3 : (x½y)* = e½x½y½xx½yy½xy½yx½… = semua
string yang merupakan concatenation dari nol atau lebih x, y, atau keduanya.
2. FINITE
STATE AUTOMATA
2.1. Definisi
Finite State Automata dinyatakan oleh 5 tuple M = (Q , S , d
, S , F ).
Keterangan :
Q = himpunan state.
S
= himpunan simbol input.
d
= fungsi transisi d
: Q ´
S.
S = state awal / initial state , S Î Q.
F = state akhir,
F Í
Q.
Contoh :
Q =
{Genap, Ganjil}
S = {0,1}
S =
Genap
F =
{Ganjil }
|
d
|
0
|
1
|
|
|
Genap
|
Genap
|
Ganjil
|
|
|
Ganjil
|
Ganjil
|
Genap
|
|
atau
d(Genap,0)
= Genap
d(Genap,1)
= Ganjil
d(Ganjil,0)
= Ganjil
d(Ganjil,1)
= Genap
Karakteristik dari Finite State Automata sebagai
berikut :
¨
Model
matematika yang dapat menerima input dan mengeluarkan output.
¨
Memiliki
state yang berhingga banyaknya dan dapat berpindah dari satu state ke state
lainnya berdasar input dan fungsi transisi.
¨
Tidak
memiliki tempat penyimpanan/memori, hanya bisa mengingat state terkini.
¨
Mekanisme
kerja dapat diaplikasikan pada : elevator, teks editor, analisa leksikal, cek
pariti.
Contoh Cek Pariti
ganjil
Misal :
1101
Genap 1 Ganjil 1 Genap
0 Genap 1 Ganjil di terima oleh mesin.
Misal :
1100
Genap 1 Ganjil 1 Genap 0 Genap 0 Genap di tolak
oleh mesin.
2.2. Jenis
Finite State Automata terdiri atas :
Deterministic Finite Automata (DFA) : dari suatu state ada tepat satu state berikutnya untuk setiap simbol masukan yang diterima,
DFA
terdiri atas :
§ Himpunan keadaan (state),
§ Alfabet atau himpunan huruf,
§ Satu keadaan awal,
§ Himpunan keadaan akhir, dan
§ Fungsi transisi.
Non-deterministic Finite Automata
(NFA) : dari suatu state ada
0, 1 atau lebih state berikutnya
untuk setiap simbol masukan yang diterima
NFA terdiri atas :
§ Himpunan keadaan (state),
§ Alfabet atau himpunan huruf,
§ Satu keadaan awal,
§ Himpunan keadaan akhir, dan
§ Relasi transisi.
Deterministic
Finite Automata
¨
Contoh : pengujian pariti ganjil.
¨
Contoh lain : pengujian untuk
menerima bit string dengan banyaknya
0 genap, serta banyaknya 1 genap.
¨
0011 : diterima.
.
¨
10010 : ditolak, karena banyaknya
0 ganjil.
¨
Diagram transisi-nya :
¨
DFA sebagai berikut :
Q =
{q0 , q1 , q2 , q3 }
S
= {0,1}
S =
q0
F =
{ q0}
fungsi transisi
|
d
|
0
|
1
|
|
q0
|
q2
|
q1
|
|
q1
|
q3
|
q0
|
|
q2
|
q0
|
q3
|
|
q3
|
q1
|
q2
|
d( q0,011) = d(
q2,11) = d( q3,1) = q2 Ditolak.
d( q0,1010) = d(
q1,010) = d( q3,10) = d(
q2,0) = q0 Diterima.
¨
Contoh lain DFA : Variabel dalam
bahasa pascal diawali oleh huruf (besar/kecil), dan diikuti dengan huruf atau
angka.
¨
Contoh DFA lainnya :
Nondeterministic
Finite Automata
*
Perbedaan dengan NFA: fungsi transisi dapat memiliki 0 atau lebih fungsi
transisi.
¨
G = ({q0 , q1 , q2
, q3, q4 }, {0,1}, d
, q0 , { q2 , q4}}
|
d
|
0
|
1
|
|
q0
|
{ q0,q3}
|
{q0,q1}
|
|
q1
|
e
|
{q2}
|
|
q2
|
{q2}
|
{q2}
|
|
q3
|
{q4}
|
e
|
|
q4
|
{q4}
|
{q4}
|
¨
String diterima NFA bila terdapat
suatu urutan transisi berdasar input, dari state awal ke state akhir.
¨
harus mencoba semua kemungkinan.
¨
Contoh : string 01001
Contoh
: FSA yang menerima bahasa {an | n³0 }
* Dua buah state dari FSA disebut
indistinguishable (tidak dapat dibedakan)
apabila :
d(q,w)ÎF sedangkan d(p,w)ÏF dan
d(q,w) ÏF sedangkan d(p,w) ÎF untuk semua w Î S*
* Dua buah state dari FSA
disebut distinguishable (dapat
dibedakan) bila terdapat w Î S*
sedemikian
hingga:
d(q,w)ÎF sedangkan d(p,w)ÏF dan
d(q,w) ÏF sedangkan d(p,w) ÎF untuk semua w Î S*
Prosedur menentukan
pasangan status indistinguishable sebagai berikut :
1. Hapus
semua state yang tak dapat dicapai dari state awal.
2. Catat
semua pasangan state (p,q) yang distinguishable, yaitu {(p,q) | p Î
F Ù
q Ï
F}.
3. Untuk
setiap pasangan (p,q) sisanya, untuk setiap aÎ S, tentukan d(p,a)
dan d(q,a).
Contoh :
1. Hapus
state yang tidak tercapai -> tidak ada.
2. Pasangan
distinguishable (q0,q4), (q1,q4),
(q2,q4), (q3,q4).
3. Pasangan
sisanya (q0,q1), (q0,q2), (q0,q3),
(q1,q2) (q1,q3) (q2,q3)
.
|
pasangan
|
state 1
|
state 2
|
Hasil
|
||
|
0
|
1
|
0
|
1
|
||
|
(q0,q1)
|
q1
|
q3
|
q2
|
q4
|
distinguishable
|
|
(q0,q2)
|
q1
|
q3
|
q1
|
q4
|
distinguishable
|
|
(q1,q2)
|
q2
|
q4
|
q1
|
q4
|
indistinguishable
|
|
(q0,q3)
|
q1
|
q3
|
q2
|
q4
|
distinguishable
|
|
(q1,q3)
|
q2
|
q4
|
q2
|
q4
|
indistinguishable
|
|
(q2,q3)
|
q1
|
q4
|
q2
|
q4
|
indistinguishable
|
Catatan : jumlah
pasangan seluruhnya :
Prosedur
Reduksi DFA sebagai berikut :
1. Tentukan
pasangan status indistinguishable.
2. Gabungkan
setiap group indistinguishable state ke dalam satu state dengan relasi
pembentukan group secara berantai : Jika p dan q indistingishable dan jika q
dan r indistinguishable maka p dan r indistinguishable, dan p,q serta r
indistinguishable semua berada dalam satu group.
3. Sesuaikan
transisi dari dan ke state-state gabungan.
Contoh
1. pasangan
status indistinguishable (q1,q2), (q1,q3) dan (q2,q3).
2. q1,q2,q3
ketiganya dapat digabung dalam satu state q123.
3. Menyesuaikan
transisi, sehingga DFA menjadi
3. Tata
Bahasa Bebas Konteks
3.1. Gambaran
Bahasa Bebas Konteks
Konsep Dasar
- Anggota
alfabet dinamakan simbol terminal.
- Kalimat
adalah deretan hingga simbol-simbol terminal.
- Bahasa
adalah himpunan kalimat-kalimat. Anggota bahasa bisa tak hingga kalimat.
- Simbol-simbol
berikut adalah simbol terminal :
ü huruf kecil, misalnya : a, b, c, 0, 1, …
ü simbol operator,
misalnya : +, -, dan ´
ü simbol tanda
baca, misalnya : (, ), dan ;
ü string yang
tercetak tebal, misalnya : if, then, dan else.
- Simbol-simbol
berikut adalah simbol non terminal
/Variabel :
ü huruf besar,
misalnya : A, B, C
ü huruf S sebagai simbol awal
ü string yang
tercetak miring, misalnya : expr .
- Huruf
yunani melambangkan string yang tersusun atas simbol-simbol terminal atau
simbol-simbol non terminal atau campuran keduanya, misalnya : a, b, dan g.
- Sebuah
produksi dilambangkan sebagai a ® b, artinya :
dalam sebuah derivasi dapat dilakukan penggantian simbol a dengan
simbol b.
- Derivasi
adalah proses pembentukan sebuah kalimat atau sentensial. Sebuah derivasi
dilambangkan sebagai : a Þ b.
- Sentensial
adalah string yang tersusun atas simbol-simbol terminal atau simbol-simbol
non terminal atau campuran keduanya.
- Kalimat
adalah string yang tersusun atas simbol-simbol terminal. Kalimat adalah
merupakan sentensial, sebaliknya belum tentu..
Deskripsi bahasa
alami :
<kalimat> ® <subjek>
<predikat>
<subjek> ® <kata benda>
<predikat> ® <kata kerja>
<kata benda> ® kucing
<kata kerja> ® berlari
<kata kerja> ® menyapu
Contoh :
·
kucing berlari.
·
kucing menyapu (sintaks yes,
semantik no).
Dalam tatabahasa
bebas konteks :
·
Ruas kiri dari aturan produksi terdiri dari satu simbol non terminal.
·
Ruas kanan dapat berupa string yang dibentuk dari simbol terminal dan
non terminal.
Contoh
S ®aSb | e
Kalimat-kalimat
yang dibangkitkan dari aturan produksi itu adalah e,ab,aabb,aaabbb,... , anbn
Contoh
A ®0A0
A ®1A1
A®a
Kalimat-kalimat yang dibangkitkan dari aturan
produksi itu adalah a,01a10, 1001a1001 , 110a011 babR
Contoh
:
S ® aSb | SS |e
Bahasa
yang dihasilkan oleh tatabahasa dengan aturan produksi di atas adalah :
L = {w Î (a + b)* |na(w)
=nb(w) }
3.2.
Leftmost dan Rightmost Derivation
Suatu penguraian /penurunan dikatakan leftmost derivation bila setiap tahapan penurunan variabel / non terminal
terkiri yang diuraikan. Apabila setiap tahapan penurunan variabel / non
terminal paling kanan yang diuraikan disebut rightmost derivation
Contoh
1 :
G=({A,B,S}, {a,b},S,P} dengan aturan produksi P :
S ® AB
A® aaA | l
B®Bb | l
Menspesifikasikan
bahasa :
L(G) = {a2nbm |
n³0 , m³0}
Leftmost
derivation untuk menghasilkan string aab
S Þ AB Þ aaAB Þ aaB Þ aaBb Þ aab
Righmost
derivation untuk menghasilkan string aab
S
Þ AB Þ ABb Þ aaABb ÞaaAb Þaab
Contoh
2 :
G=({A,B,S}, {a,b},S,P} dengan aturan produksi P :
S ® aAB
A® bBb
B® A | l
Leftmost
derivation untuk menghasilkan string abbbb
S Þ aAB Þ abBbB Þ abAbB Þ abbBbbB
Þ abbbbB Þ abbbb
Righmost
derivation untuk menghasilkan string abbbb
S Þ aAB Þ aA Þ abBb Þ abAb Þ abbBbb Þ abbbb
3.3.
Pohon Urai
Untuk menampilkan penguraian, dapat dilakukan dengan
membentuk pohon urai (sayangnya, urutan penguraian tidak terlihat).
Contoh :
3.4.
Parsing dan Keanggotaan
Untuk menentukan apakah string w berada di L(G),
dengan cara secara sistematis membangun semua kemungkinan penurunan, dan
mencocokkan hasilnya apakah ada yang sama dengan string w. (disebut exhaustive search parsing)
Contoh
:
Menentukan apakah string ab berada pada bahasa yang
dibentuk oleh grammar dengan aturan produksi S ® SS | aSb | bSa | l.
Untuk
penguraian pertama :
1. S Þ SS
2. S Þ aSb
3. S Þ bSa
4. S Þ l
Penguraian nomor 3 dan 4 tidak perlu dilanjutkan.
Penguraian 1 dan Penguraian 2 terbentuk sebagai berikut :
1a.
S Þ SS Þ SSS 2a. S Þ aSb Þ aSSb
1b.
S Þ SS Þ aSbS 2b. S
Þ aSb Þ aaSbb
1c.
S Þ SS Þ bSaS 2c. S Þ aSb Þ abSab
1d.
S Þ SS Þ S 2d. S Þ aSb Þ ab
3.5.
Ambiguitas pada Tatabahasa dan Bahasa
Tatabahasa bebas konteks G disebut ambigu
jika terdapat beberapa w Î L(G) yang mempunyai paling
sedikit dua buah pohon penurunan
Contoh
:
Tatabahasa
dengan aturan produksi S ® SS | aSb | l.
string
aabb mempunyai 2 pohon penurunan :
3.6.
Pumping Lemma untuk bahasa bebas konteks
¨
Jika suatu rangkaian simbol / string yang cukup panjang yang merupakan
sebuah bahasa bebas konteks, maka kita dapat menemukan dua substring yang
jaraknya berdekatan yang jika dipompa, string baru yang diperoleh merupakan
bahasa bebas konteks juga.
¨
Secara formal, lemma di atas dinyatakan dengan
¨
Syarat “ kedua lokasi berdekatan” dinyatakan dengan kondisi |vwx| £ n.
¨
Jika salah satu v atau x diambil sebagai string kosong, maka lemma
diatas berubah menjadi lemma untuk bahasa reguler
Contoh :
Tatabahasa
dengan aturan produksi
S ®uAy
A ® vAx
A ® w
maka aturan derivasinya sebagai berikut :
S Þ uAy Þ uwy
S Þ uAy Þ uvAxy Þuvwxy
S Þ uAy Þ uvAxy Þ uvvAxxy Þuvvwxxy
sehingga
untuk setiap i ³0 , uviwxiy
Î L.
3.7.
Sifat sifat tertutup bahasa bebas konteks
¨
Gabungan dua CFL merupakan CFL juga.
Jika
diketahui dua buah CFG G1= (N1,T1,S1,P1)
dan G2=(N2,T2,S2,P2)
yang menghasilkan bahasa L1 dan L2 , maka CFG L1 È
L2 dapat dibentuk dengan cara :
1.
Menggabungkan
kedua himpunan dan menambahkan satu simbol variabel baru S
2.
Menggabungkan
kedua himpunan simbol terminal
3.
Menggabungkan
kedua himpunan aturan produksi dan menambahkan satu aturan produksi baru
S ® S1|S2
yang digunakan untuk memilih salah satu simbol awal S1 atau S2
dari simbol awal baru S
G3
= (N1ÈN2È{S},T1ÈT2
,S,P1ÈP2 È{S®S1|S2}}
¨
Penyambungan
dua CFL merupakan CFL juga.
Jika diketahui dua buah
CFG G1= (N1,T1,S1,P1)
dan G2=(N2,T2,S2,P2)
yang menghasilkan bahasa L1 dan L2 , maka bahasa L1L2 dapat
dibentuk oleh :
G4
= (N1ÈN2È{S},T1ÈT2
,S,P1ÈP2 È{S®S1S2}}
¨
Klosure
Kleene dari CFL adalah CFL juga.
Klosure
Kleene dari tatabahasa G=(N,T,S1,P) adalah
G5
= (N È
{S} , T , S , P È {S ® S1S
| e
} )
¨
Bahasa
bebas konteks tertutup terhadap substitusi
Contoh
:
La
= {0 n1n | n ³1 } dan Lb
= { wwR | w Î (0+2)* }
dihasilkan
oleh tatabahasa Ga dengan aturan produksi
Sa ®
0Sa1 | 01 serta tatabahasa G2 dengan aturan produksi Sb ®
0Sb0 | 2Sb2 | e.
Didefinisikan
tatabahasa G dengan aturan produksi S ® aSbS | bSaS | e
Jika f adalah
substitusi f(a)= La dan f(b) = Lb maka f(L) adalah bahasa yang dihasilkan oleh
tatabahasa dengan aturan produksi :
S ® SaSSbS | SbSSaS
| e
Sa
® 0Sa1 | 01
Sb
® 0Sb0 | 2Sb2 | e
Tatabahasa Bebas Konteks dan Bahasa Pemrograman
¨
Tatabahasa bebas konteks digunakan untuk
mendefinisikan sintaks bahasa pemrograman.
¨
Menggunakan notasi BNF (Backus-Naur Form).
¨
Variabel / non terminal : <...> .
¨
Terminal : tanpa tanda.
¨
¬
diganti dengan ::=
¨
Contoh :
Statement if
then else
< if_statement> ::= if <expression>
<then_clause>
<else_clause>
4. PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS
4.1. Tujuan
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:
- Penghilangan produksi useless ( tidak berguna ).
- Penghilangan produksi unit.
- Penghilangan produksi ε .
4.2. Penghilangan Produksi Useless
Di sini produksi useless didefinisikan sebagai :
·
Produksi yang memuat simbol 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 :
§
Aturan produksi A à
D, simbol variabel D tidak memiliki penurunan.
§
Aturan produksi C à
bb, Penurunan dari simbol S, dengan jalan manapun tidak akan pernah mencapai C.
§
Simbol variabel E tidak memiliki aturan produksi
yang menuju terminal.
§
Konsekuensi no (3) Aturan produksi B à E, simbol variabel E
tidak memiliki penurunan.
§
Produksi yang useless:
A à
D
C à
bb
E à
aEa
B à
E
Penyederhanaannya menjadi:
S à
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
Analisa :
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 tidak 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 :
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
Contoh 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.
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
C à
ef
D à
dd
Contoh :
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 :
S à
Cba | D
A à
bbC
B à
Sc | ddd
C à
eAn | f | C
D à
E | SABC
E à
gh
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
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 :
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 à
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.
5. BENTUK NORMAL CHOMSKY
5.1. Definisi Bentuk Normal Chomsky
Bentuk
normal Chomsky / Chomsky Normal Form (CNF) merupakan salah satu bentuk normal yang
sangat berguna untuk tata bahasa bebas konteks ( CFG ). Bentuk normal Chomsky dapat dibuat dari sebuah tata bahasa bebas
konteks yang telah mengalami penyederhanaan yaitu penghilangan produksi useless, unit, dan ε. Dengan kata lain,
suatu tata bahasa bebas konteks dapat dibuat menjadi bentuk normal Chomsky dengan syarat tata bahasa bebas konteks
tersebut:
·
Tidak memiliki produksi useless
·
Tidak memiliki produksi unit
·
Tidak memiliki produksi ε
Aturan produksi dalam bentuk normal Chomsky ruas kanannya tepat
berupa sebuah terminal atau dua variabel. Misal :
A à BC
A à b
B à a
C à BA | d
Pembentukan Bentuk Normal Chomsky
Langkah-langkah pembentukan bentuk normal Chomsky secara umum sebagai berikut:
·
Biarkan aturan produksi yang sudah dalam bentuk normal Chomsky .
·
Lakukan penggantian aturan produksi yang ruas
kanannya memuat simbol terminal dan panjang ruas kanan > 1.
·
Lakukan penggantian aturan produksi yang ruas
kanannya memuat > 2 simbol variabel.
·
Penggantian-penggantian tersebut bisa dilakukan
berkali-kali sampai akhirnya semua aturan produksi dalam bentuk normal Chomsky .
·
Selama dilakukan penggantian, kemungkinan kita
akan memperoleh aturan-aturan produksi baru, dan juga memunculkan simbol-simbol
variabel baru
Contoh, tata bahasa bebas konteks ( kita anggap tata
bahasa bebas konteks pada bab ini sudah mengalami penyederhanaan ) :
S à bA | aB
A à bAA | aS | a
B à
aBB | bS | b
Aturan
produksi yang sudah dalam bentuk
normal Chomsky :
A à a
B à
b
Dilakukan penggantian aturan produksi yang belum bentuk normal Chomsky (‘=>’ bisa
dibaca berubah menjadi) :
S à
bA => S à P1A
S à
aB => S à P1B
A à
bAA => S à P1AA
=> A à P1P3
A à aS => A à P2S
B à
aBB => B à P2BB
=> B à P2P4
B à
bS => B à P1S
Terbentuk aturan produksi dan simbol variabel baru :
P1 à
b
P2 à
a
P3 à
AA
P4 à
BB
Hasil akhir aturan produksi dalam bentuk
normal Chomsky :
A à a
B à b
S à P1A
S à P2B
A à P1P3
A à P2S
B à P2P4
B à P1S
P1 à b
P2 à a
P3 à AA
P4 à
BB
Contoh, tata
bahasa bebas konteks:
S à aB | CA
A à a | bc
B à BC | Ab
C à aB | b
Aturan
produksi yang sudah dalam bentuk normal
Chomsky :
S à CA
A à a
B à BC
C à b
Penggantian aturan produksi yang belum dalam bentuk normal Chomsky :
S à
aB => S à P1B
A à
bc => S à P2P3
B à
Ab => B à A
P2
C à
aB => C à P1B
Terbentuk aturan produksi dan simbol variabel baru :
P1 à
a
P2 à
b
P3 à
c
Hasil akhir
aturan produksi dalam bentuk
normal Chomsky :
S à CA
A à a
B à BC
C à b
S à P1B
S à P2P3
B à A P2
C à P1B
P1 à a
P2 à b
P3 à c
Contoh :
Tata bahasa bebas konteks :
S à aAB | ch | CD
A à dbE | eEC
B à ff | DD
C à ADB | aS
D à i
E à jD
Aturan produksi yang sudah dalam bentuk normal Chomsky :
S à CD
B à DD
D à i
Penggantian aturan produksi:
S à
aAB => S à P1P2
S à
ch => S à P3P4
A à
dbE => A à P5P6
A à
eEC => A à P8P9
B à
ff => B à P10P10
C à
ADB => C à
AP11
C à
aS => C à P1S
E à
jD => E à P12D
Terbentuk aturan produksi baru:
P1 à
a
P2 à
AB
P3 à
c
P4 à
h
P5 à
d
P6 à
P7E
P7 à
b
P8 à
e
P9 à
EC
P10 à
f
P11 à
DB
P12 à
j
Hasil akhir dalam bentuk
normal Chomsky:
S à CD
B à DD
D à i
D à i
S à P1P2
S à P3P4
A à P5P6
A à P8P9
B à P10P10
C à AP11
C à P1S
E à P12D
P1 à a
P2 à AB
P3 à c
P4 à h
P5 à d
P6 à P7E
P7 à b
P8 à e
P9 à EC
P10 à f
P11 à DB
P12 à j
4.2. Algoritma
CYK untuk Tata Bahasa Bebas Konteks
Algoritma
CYK merupakan algoritma parsing dan
keanggotaan ( membership) untuk tata
bahasa bebas konteks. Algortima ini diciptakan oleh J. Cocke, DH. Younger, dan T.
Kasami. Syarat untuk penggunaan
algortima ini adalah tata bahasa harus berada dalam bentuk normal Chomsky .
Obyektivitas dari algortima ini untuk menunjukkan apakah suatu string dapat diperoleh dari suatu tata
bahasa.
Algoritma CYK sebagai berikut:
begin
1)
for i:= 1 to n do
2)
Vi1 := {A| A à a aturan produksi dimana simbol ke- i adalah
a };
3)
for j:= 2 to n do
4)
for i:= 1
to (n-j+1) do
begin
5)
Vij:=Ø;
6)
for
k:=1 to (j – 1) do
7)
Vij:= Vij υ (
A | A à BC adalah suatu
produksi, dimana B di Vik dan C di Vi+k,j-k }
end
end
Penjelasan:
·
n
= panjang untai yang akan diperiksa, missal : untuk
untai ‘ada’, n = | ada | =3
·
i akan menyatakan kolom ke-
·
j
akan
menyatakan baris ke-
·
tahapan no (1) dan (2) untuk
mengisi table baris pertama kolom 1 – n
·
no (3), interasi dari baris ke- 2 sampai n
·
no (4), interasi untuk mengisi
kolom 1 sampai ( n – baris + 1) pada suatu baris.
·
no (5) inisialisasi Vij dengan
Ø
·
no (6) dan no (7), interasi untuk memeriksa
mana saja yang menjadi anggota Vij
6.
PENGHILANGAN REKURSIF KIRI
6.1. 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.
Keterangan :
β=(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,
Contoh :
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.
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.
6.2. Tahapan Penghilangan Rekursif Kiri
Langkah-langkah
penghilangan rekursif kiri sebagai berikut :
§
Pisahkan aturan produksi yang
rekursif kiri dan yang tidak, missal :
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:
ü
A
à β1Z
| β2Z | .... βmZ
ü
Z
à α1 | α2 | α3 | .... αn
ü
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 produksi semula
yang tidak rekursif kiri.
Contoh :
Ttata bahasa bebas konteks :
S à
Sab | aSc |dd | ff | Sbd
Pertama-tama kita lakukan
pemisahan aturan produksi
Aturan produksi yang rekursif
kiri : S à
Sab | Sbd
Dari situ kita tentukan :
Untuk simbol ruas kiri sebagai
berikut S : α1 = ab, α2 = bd
Aturan produksi yang tidak
rekursif kiri : S à
aSc | dd | ff
Dari situ kita dapatkan:
Untuk simbol ruas kiri sebagai
berikut : S : β1 = aSc, β2 = dd, β3 = ff
Kita lakukan penggantian aturan
produksi yang rekursif kiri:
Untuk yang memiliki simbol ruas
kiri S:
S à
Sab | Sbd, digantikan oleh:
S à aScZ1 | dd Z1
| ffZ1
Z1 à ab | bd
Z1 à abZ1 | bd Z1
Hasil akhir setelah penghilangan rekursif kiri
adalah:
S à aSc | dd | ff
S à aScZ1 | dd
Z1 | ffZ1
Z1 à ab | bd
Z1 à abZ1 | bd Z1
Pada kasus di atas S adalah
satu-satunya simbol variabel yang menghasilkan produksi rekursif kiri.
Contoh lain, terdapat tata bahasa
bebas konteks:
S à Sab | Sb | cA
A à Aa | a | bd
Pertama-tama kita lakukan
pemisahan aturan produksi
Aturan produksi yang rekursif
kiri :
S à Sab | Sb
A à Aa
Dari situ kita tentukan:
Untuk simbol ruas kiri S: α1=
ab, α2 =b
Untuk simbol ruas kiri A: α1
= a
Aturan produksi yang tidak
rekursif kiri :
S à
cA
A à
a | bd
Dari situ kita dapatkan
Untuk simbol ruas kiri S: β1
= cA
Untuk simbol ruas kiri A: β1 = a, β2 =
bd
Kita lakukan penggantian aturan
produksi yang rekursif kiri:
Untuk yang memiliki simbol ruas
kiri S :
S à
Sab | Sb, digantikan oleh :
S à
cAZ1
Z1 à ab | b
Z1
à abZ1 |
bZ1
Untuk yang memiliki simbol ruas kiri A :
A à
Aa, digantikan oleh:
A à
a Z2 | bdZ2
Z2 à
a
Z2 à
a Z2
Hasil akhir setelah
penghilangan rekursif kiri adalah:
S à cA
A à a | bd
S à cAZ1
Z1 à ab | b
Z1 à abZ1 | bZ1
A à a Z2 | bdZ2
Z2 à a
Z2 à a Z2
Perhatikan
bahwa penghilangan rekursif kiri memunculkan simbol variabel baru, dan aturan
produksi baru yang rekursif kanan.
Contoh
lain, terdapat tata bahasa bebas konteks:
S à
Sa |aAc | c | ε
A à
Ab | ba
Pertama-tama
kita lakukan pemisahan aturan produksi
Aturan
produksi yang rekursif kiri:
S à
Sa
A à
Ab
Dari
situ kita tentukan:
Untuk
simbol ruas kiri S: α1 = a
Untuk
simbol ruas kiri A: α1 = b
Aturan
produksi yang tidak rekursif kiri:
S à
aAc | c | ε
A à
ba
Dari
situ kita dapatkan
untuk
simbol ruas kiri S:β1 = aAc, β2= c, β3 = ε
untuk
simbol ruas kiri A: β1 = ba
Perhatikan
produksi ε termasuk produksi yang tidak rekursif kiri
Kita
lakukan penggantian aturan produksi yang rekursif kiri :
Untuk
yang memilki simbol ruas kiri S :
S
à Sa, digantikan
oleh :
S à
aAcZ1 | cZ1 | Z1
Z1 à
a
Z1 à
a Z1
Untuk
yang memiliki simbol ruas kiri A:
A
à Ab, digantikan
oleh :
A à
ba Z2
Z2 à
b
Z2 à
bZ2
Hasil akhir setelah penghilangan
rekursif kiri adalah:
S à
aAc | c | ε
S à
aAcZ1 | cZ1 | Z1
A à
ba
A à
ba Z2
Z1 à a
Z1 à a Z1
Z2 à b
Z2 à b Z2
7. BENTUK NORMAL GREIBACH
7.1. Definisi Bentuk Normal Greibach
Bentuk normal Greibach
merupakan bentuk normal yang
memiliki banyak konsekuensi teoritis dan prkatis. Dalam bentuk normal Greibach kita membatasi posisi munculnya
terminal-terminal dan variabel-variabel. Suatu tata bahasa bebas konteks (CFG)
dikatakan dalam bentuk normal Greibach
/ Greibach Normal Form, selanjutnya kita sebut sebagai GNF, jika
setiap aturan produksinya ada dalam bentuk:
A à aα
Keterangan :
A : simbol terminal (tunggal), a ε T
Α : rangkaian simbol-simbol variabel (V*)
Atau dengan kata lain, suatu tata bahasa bebas
konteks dalam bentuk normal Greibach bila hasil produksinya (ruas kanan)
diawali dengan satu simbol terminal, slanjutnya bisa diikuti oleh rangkaian
simbol variabel. Contoh tata bahasa bebas konteks dalam bentuk bentuk normal Greibach:
S à
a | aAB
A à aB
B à cS
Untuk dapat diubah ke dalam bentuk
normaol Greibach, tata bahasa semula haru memenuhi syarat:
- Sudah dalam bentuk normal Chomsky
- Tidak bersifat rekursif kiri
- Tidak menghasilkan ε
Terdapat
dua cara pembentukan bentuk normal Greibach , yaitu melalui substitusi
dan perkalian matriks. Pada bagian berikutnya kita membahasa kedua cara
tersebut.
7.2.
Pembentukan Bentuk Normal Greibach dengan Substitusi
Secara
umum langkah-langkah untuk mendapatkan bentuk normal Greibach :
1.
Tentukan urutan simbol-simbol
variabel yang ada dalam tata bahasa. Misalkan terdapat m variabel dengan
urutan A1, A2, ...., Am
2.
Berdasarkan urutan simbol yang
ditetapkan pada langkah (1) seluruh aturan produksi yang ruas kanannya diawali
dengan simbol variabel dapat dituliskan dalam bentuk Ah à
Ai γ di mana h <> i (rekrusif kiri sudah dihilangkan),
γ bisa berupa simbol-simbol variabel :
a.
Jika
h < i, aturan produksu ini sudah benar ( tidakperlu diubah)
b.
Jika
h > i, aturan produksi belum benar. Lakukan substitusi
berulang-ulang terhadap Ai (ganti Ai pada produksi ini
dengan ruas kanan produksi dari variabel Ai ) sehingga suatu saat
diperoleh produksi dalam bentuk Ah à Ap γ (dimana h
£ p )
i)
Jika
h = p , lakukan penghilangan rekursif kiri
ii)
Jika h < p, aturan produksi
sudah benar
3.
Jika
terjadi penghilangan rekursif kiri pada tahap (2b), sejumlah simbol variabel
baru yang muncul dari operasi ini dapat disisipkan pada urutan variabelsemula
dimana saja asalkan ditempatkan tidak sebelum Ah (di kiri)
4.
Setelah
langkah (2) & (3) dikerjakan maka aturan-aturan produksi yang ruas kanannya
dimulai simbol variabel sudah berada dalam urutan yang benar
Ax
à
Ay g
( di mana x < y )
Produksi-produksi
yang lain ada dalam bentuk:
Ax
à
a g
( a = simbol terminal )
Bx
à
g
(
B2 = simbol variabel baru yang akan muncul sebagai akibat dari
operasi penghilangan rekursif kiri ).
5.
Bentuk normal Greibach diperoleh dengan cara melakukan substitusi
mundur mulai dari variabel Am, lalu Am-1, Am-2,
..... Dengan cara ini aturan produksi dalam bentuk Ax à Ay g dapat diubah sehinga ruas
kanannya dimulai dengan simbol terminal.
6.
Produksi
dalam bentuk Bx à g juga dapat diubah dengan cara
substitusi seperti pada langkah (5).
Contoh (tata bahasa
bebas konteks sudah dalam bentuk normal Chomsky dan memenuhi syarat
untuk diubah ke bentuk normal Greibach), simbol awal adalah S:
S à
CA
A à
a | d
B à
b
C à
DD
D à
AB
Kita tentukan urutan
simbol variabel, misalnya S, A, B, C, D (S<A<B<C<D).
* Perhatikan urutan
tersebut boleh anda tentukan sendiri, buatlah urutan sedemikian sehingga
memudahkan untuk proses selanjutnya
Kita periksa aturan
produksi yang simbol pertama pada ruas kanan adalah simbol variabel, apakah
sudah memenuhi ketentuan urutan variabel:
§ S à CA ( sudah memenuhi aturan
karena S<C)
§ C à DD (sudah memenuhi karena
C<D)
§ D à AB (tidak memenuhi, karena
D>A)
Yang belum memenuhi
urutan yang telah kita tentukan adalah: D à AB, karena ruas
kiri > simbol pertama pada ruas kanan. Maka kita lakukan sibstitusi pada
simbol variabel A, aturan produksi menjadi :
D
à
aB | dB
Setelah
semua aturan produksi sudah memenuhi ketentuan urutan variabel, kita lakukan
substitusi mundur pada aturan produksi yang belum dalam bentuk normal
Greibach (‘=>’ dibaca ‘menjadi’):
§ C à DD => C à aBD | dBD
§ S à CA => S à aBDA | dBDA
* Perhatikan substitusi
mundur dimulai dari aturan produksi yang memiliki ruas kiri dengan urutan
variabel paling akhir ( kasus di atas:S<A<B<C<D, maka C lebih dulu
disubstitusikan daripada S ).
Hasil akhir aturan
produksi yang sudah dalam bentuk normal Greibach :
S à
aBDA | dBDA
A à
a | d
B à
b
C à
aBD | dBD
D à
aB | dB
* Perhatikan : setiap
substitusi kita lakukan pada simbol variabel pertamapada ruas kanan ( pada
aturan produksi yang belum bentuk normal Greibach tentunya ).
Prinsipnya
:
- Biarkan
aturan produksi yang sudah dalam bentuk normal Greibach
- Tentukan
pengurutan simbol variabel, berdasarkan kondisi aturan produksi yang ada
buatlah urutan sedemikian sehingga memudahkan untuk proses selanjutnya.
Mulailah terlebih dahulu dari seimbol awal.
§
Lakukan
perubahan pada aturan produksi yang belum memenuhi ketentuan urutan tersebut
dan bila perlu selama proses itu bisa dilakukan substitusi dan penghilangan
rekursif kiri.
- Lakukan
substitusi mundur sedemikian rupa sehingga semua aturan produksi akan
diawali dengan tepat sebuah simbol terminal. Proses substitusi mundur
dimulai dari aturan produksi dengan urutan paling akhir.
- Lakukan
substitusi mundur juga pada aturan produksi baru yang muncul sebagai hasil
penghilangan rekursif kiri.
Contoh (simbol awal A) :
A à
BC
B à
CA | b
C à
AB | a
Kita tentukan urutan
simbol: A,B,C ( A<B<C )
A à
BC ( sudah memenuhi karena A<B)
B à
CA (sudah memenuhi karena B<C)
C à
AB (padahal C > A sehingga harus diubah)
Pengubahan C à
AB:
C à
AB => C à
BCB => C à
CACB | bCB
Untuk C à
CACB lakukan penghilangan rekursif kiri menjadi
C
à bCBZ1 | aZ1
Z1
à ACB
Z1
à ACBZ1
Kita lihat seluruh
hasil produksi dari variabel C, sudah dalam bentuk normal Greibach:
C à
bCBZ1 | aZ1 | bCB | a
Setelah semua aturan
produksi sudah memenuhi ketentuan urutan variabel, kita laukan substitusi
mundur:
B à
CA => B à
bCBZ1A | aZ1A | bCBA | aA
A à
BC => A à
bCBZ1AC | aZ1AC | bCBAC | aAC | bC
Selanjutnya lakukan
pula substitusi pada aturan produksi dengan variabel baru yang terbentuk (pada contoh
ini Z1) :
§ Z1 à ACB => Z1 à bCBZ1ACCB | aZ1ACCB
| bCBACCB | aACCB | bCCB
§ Z1 à ACBZ1 => Z1
à bCBZ1ACCBZ1
| aZ1ACCBZ1 | bCBACCBZ1 | aACCBZ1 |
bCCBZ1
Hasil akhir aturan
produksi dalam bentuk bentuk normal Greibach :
A à
bCBZ1AC | aZ1AC | bCBAC | aAC | bC |
B à
bCBZ1A | aZ1A | bCBA | aA | B
C à
bCBZ1 | aZ1 | bCB | a
Z1 à
bCBZ1ACCB | aZ1ACCB | bCBACCB | aACCB | bCCB
Z1 à
bCBZ1ACCBZ1 | aZ1ACCBZ1 | bCBACCBZ1
| aACCBZ1 | bCCBZ1
Sumber Pustaka :
Teori Bahasa dan
Otomata, Heru Cahya Rustamadji, Fakultas Teknik Industri Universitas
Pembangunan Nasional, 2004.
Computation Engineering
: Applied Automata Theory and Logic, Gopalakrishnan, Ganesh, New York :
Springer, 2006.
Introduction to
Automata Theory, Languages, and Computation, 2nd Edition, Hopcroft,
John E. et al, New York : Addison-Wesley, 2001.
Tentang
Penulis
Adi S. Nugroho, lahir
pada tanggal 25 Januari 1973, merupakan alumni dari STMIK (STI & K) Jakarta
dan Universitas Krisnadwipayana. Menamatkan jenjang S1 pada bulan Pebruari 1996
dan menamatkan jenjang S2 pada bulan Maret 1999.
Sebelum menekuni
profesi sebagai dosen, pernah bekerja pada sebuah bank swasta nasional hingga
mencapai posisi yang cukup tinggi, sebagai Management Information System (MIS)
and Helpdesk Manager, juga pernah mengepalai Laboratorium Komputer di suatu SMK
swasta nasional, dan terakhir adalah menduduki posisi sebagai HRD and GA
Manager pada sebuah bengkel mobil Suzuki.
1. MENGENAL OTOMATA
1.1. Definisi Otomata
Otomata adalah mesin
abstrak yang dapat mengenali (recognize),
menerima (accept), atau membangkitkan
(generate) sebuah kalimat dalam
bahasa tertentu.
Sedangkan
arti Otomata menurut American Heritage Dictionary:
1.
a robot.
2.
one that behaves in an automatic or mechanical fashion.
Sementara
dalam dunia matematika, Otomata berkaitan dengan teori mesin abstrak, yaitu
mesin sekuensial yang menerima input, dan mengeluarkan output, dalam bentuk
diskrit. Contoh :
♦ Mesin Jaja / vending machine.
♦ Kunci kombinasi.
♦ Parser/compiler.
1.2. Pengguna Pertama Istilah Otomata
Istilah Otomata
pertama kali tercantum dalam makalah yang berjudul “The Logical and General
Theory of Automata”. Makalah ini ditulis oleh John Von Neumann dari The Institute for Advanced Study dan
disajikan di Hixon Simposium pada tanggal 20 September 1948 di Pasadena,
Kalifornia, Amerika Serikat.
1.3. Buku
Otomata Pertama
Sebagai
kelanjutan dari makalah tersebut, John Von Neumann menulis buku yang berjudul
“Theory of Self-Reproducing Automata”. Buku ini diterbitkan oleh University of
Illinois Press pada tahun 1966.
1.4. Dasar-Dasar
Otomata
Secara garis
besar, otomata mempunyai beberapa dasar, yaitu :
• Simbol adalah sebuah entitas abstrak (seperti halnya pengertian titik dalam
geometri). Sebuah huruf atau sebuah angka adalah contoh simbol.
• String adalah deretan terbatas (finite)
simbol-simbol. Sebagai contoh, jika a, b, dan c adalah tiga buah simbol maka abcb
adalah sebuah string yang dibangun dari
ketiga simbol tersebut.
• Jika w adalah sebuah string maka panjang string dinyatakan sebagai |w| dan
didefinisikan sebagai cacahan (banyaknya) simbol yang menyusun string tersebut.
Sebagai contoh, jika w = abcb maka |w| = 4.
• String hampa adalah sebuah string dengan nol buah simbol. String
hampa dinyatakan dengan simbol ε (atau
^) sehingga |ε| = 0. String hampa dapat dipandang sebagai simbol hampa karena
keduanya tersusun dari nol buah simbol.
• Alfabet adalah hinpunan hingga (finite set) simbol-simbol.
Operasi Dasar String
Diberikan
dua string : x = abc, dan y = 123
·
Prefik string w adalah string yang dihasilkan dari
string w dengan menghilangkan nol atau lebih simbol-simbol paling
belakang dari string w tersebut.
Contoh : abc, ab,
a, dan e adalah semua
Prefix(x)
·
ProperPrefix string w adalah
string yang dihasilkan dari string w
dengan menghilangkan satu atau lebih
simbol-simbol paling belakang dari string w
tersebut.
Contoh : ab, a,
dan e adalah semua ProperPrefix(x)
·
Postfix (atau Sufix) string w
adalah string yang dihasilkan dari string w
dengan menghilangkan nol atau lebih
simbol-simbol paling depan dari string w
tersebut.
Contoh : abc, bc,
c, dan e adalah semua
Postfix(x)
·
ProperPostfix (atau PoperSufix) string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau
lebih simbol-simbol paling depan dari string w tersebut.
Contoh : bc, c,
dan e adalah semua ProperPostfix(x)
·
Head string w adalah simbol paling depan dari string w.
Contoh
: a adalah Head(x)
·
Tail string w adalah string yang dihasilkan dari string w dengan menghilangkan simbol paling depan dari string w tersebut.
Contoh : bc
adalah Tail(x)
·
Substring string w adalah string yang dihasilkan dari
string w dengan menghilangkan nol atau lebih simbol-simbol paling
depan dan/atau simbol-simbol paling belakang dari string w tersebut.
Contoh : abc,
ab, bc, a, b,
c, dan e
adalah semua Substring(x)
·
ProperSubstring string w adalah string yang dihasilkan dari
string w dengan menghilangkan satu atau lebih simbol-simbol paling
depan dan/atau simbol-simbol paling belakang dari string w tersebut.
Contoh : ab,
bc, a, b, c, dan e
adalah semua Substring(x)
·
Subsequence string w adalah string yang dihasilkan dari
string w dengan menghilangkan nol atau lebih simbol-simbol dari string
w tersebut.
Contoh : abc, ab, bc,
ac, a, b, c, dan e
adalah semua Subsequence(x)
·
ProperSubsequence string w adalah string yang dihasilkan dari
string w dengan menghilangkan satu atau lebih simbol-simbol dari
string w tersebut.
Contoh : ab,
bc, ac, a, b,
c, dan e
adalah semua Subsequence(x)
·
Concatenation adalah penyambungan
dua buah string. Operator concatenation adalah concate atau tanpa lambang apapun.
Contoh : concate(xy)
= xy = abc123
·
Alternation adalah pilihan satu di antara dua buah string. Operator
alternation adalah alternate atau ½.
Contoh :
alternate(xy) = x½y
=
abc atau 123
·
Kleene Closure : x* = e½x½xx½xxx½… = e½x½x
½x
½…
·
Positive Closure : x
= x½xx½xxx½… = x½x
½x
½…
Beberapa Sifat Operasi
·
Tidak selalu berlaku : x = Prefix(x)Postfix(x).
·
Selalu berlaku : x = Head(x)Tail(x).
·
Tidak selalu berlaku : Prefix(x) = Postfix(x) atau Prefix(x) ¹
Postfix(x).
·
Selalu berlaku : ProperPrefix(x)
¹ ProperPostfix(x).
·
Selalu berlaku : Head(x) ¹ Tail(x).
·
Setiap Prefix(x), ProperPrefix(x), Postfix(x),
ProperPostfix(x), Head(x), dan Tail(x) adalah Substring(x),
tetapi tidak sebaliknya.
·
Setiap Substring(x) adalah Subsequence(x), tetapi tidak sebaliknya.
·
Dua sifat aljabar concatenation :
¨
Operasi concatenation bersifat
asosiatif : x(yz) = (xy)z.
¨
Elemen identitas operasi
concatenation adalah e : ex = xe = x.
·
Tiga sifat aljabar alternation :
¨
Operasi alternation bersifat
komutatif : x½y
= y½x.
¨
Operasi alternation bersifat asosiatif : x½(y½z) = (x½y)½z.
¨
Elemen identitas operasi
alternation adalah dirinya sendiri : x½x
= x.
·
Sifat distributif concatenation
terhadap alternation : x (y½z) = xy½xz.
·
Beberapa kesamaan :
¨
Kesamaan ke-1 : (x*)* = x*.
¨
Kesamaan ke-2 : e½x
= x
½e = x*.
¨
Kesamaan ke-3 : (x½y)* = e½x½y½xx½yy½xy½yx½… = semua
string yang merupakan concatenation dari nol atau lebih x, y, atau keduanya.
2. FINITE
STATE AUTOMATA
2.1. Definisi
Finite State Automata dinyatakan oleh 5 tuple M = (Q , S , d
, S , F ).
Keterangan :
Q = himpunan state.
S
= himpunan simbol input.
d
= fungsi transisi d
: Q ´
S.
S = state awal / initial state , S Î Q.
F = state akhir,
F Í
Q.
Contoh :
Q =
{Genap, Ganjil}
S = {0,1}
S =
Genap
F =
{Ganjil }
|
d
|
0
|
1
|
|
|
Genap
|
Genap
|
Ganjil
|
|
|
Ganjil
|
Ganjil
|
Genap
|
|
atau
d(Genap,0)
= Genap
d(Genap,1)
= Ganjil
d(Ganjil,0)
= Ganjil
d(Ganjil,1)
= Genap
Karakteristik dari Finite State Automata sebagai
berikut :
¨
Model
matematika yang dapat menerima input dan mengeluarkan output.
¨
Memiliki
state yang berhingga banyaknya dan dapat berpindah dari satu state ke state
lainnya berdasar input dan fungsi transisi.
¨
Tidak
memiliki tempat penyimpanan/memori, hanya bisa mengingat state terkini.
¨
Mekanisme
kerja dapat diaplikasikan pada : elevator, teks editor, analisa leksikal, cek
pariti.
Contoh Cek Pariti
ganjil
Misal :
1101
Genap 1 Ganjil 1 Genap
0 Genap 1 Ganjil di terima oleh mesin.
Misal :
1100
Genap 1 Ganjil 1 Genap 0 Genap 0 Genap di tolak
oleh mesin.
2.2. Jenis
Finite State Automata terdiri atas :
Deterministic Finite Automata (DFA) : dari suatu state ada tepat satu state berikutnya untuk setiap simbol masukan yang diterima,
DFA
terdiri atas :
§ Himpunan keadaan (state),
§ Alfabet atau himpunan huruf,
§ Satu keadaan awal,
§ Himpunan keadaan akhir, dan
§ Fungsi transisi.
Non-deterministic Finite Automata
(NFA) : dari suatu state ada
0, 1 atau lebih state berikutnya
untuk setiap simbol masukan yang diterima
NFA terdiri atas :
§ Himpunan keadaan (state),
§ Alfabet atau himpunan huruf,
§ Satu keadaan awal,
§ Himpunan keadaan akhir, dan
§ Relasi transisi.
Deterministic
Finite Automata
¨
Contoh : pengujian pariti ganjil.
¨
Contoh lain : pengujian untuk
menerima bit string dengan banyaknya
0 genap, serta banyaknya 1 genap.
¨
0011 : diterima.
.
¨
10010 : ditolak, karena banyaknya
0 ganjil.
¨
Diagram transisi-nya :
¨
DFA sebagai berikut :
Q =
{q0 , q1 , q2 , q3 }
S
= {0,1}
S =
q0
F =
{ q0}
fungsi transisi
|
d
|
0
|
1
|
|
q0
|
q2
|
q1
|
|
q1
|
q3
|
q0
|
|
q2
|
q0
|
q3
|
|
q3
|
q1
|
q2
|
d( q0,011) = d(
q2,11) = d( q3,1) = q2 Ditolak.
d( q0,1010) = d(
q1,010) = d( q3,10) = d(
q2,0) = q0 Diterima.
¨
Contoh lain DFA : Variabel dalam
bahasa pascal diawali oleh huruf (besar/kecil), dan diikuti dengan huruf atau
angka.
¨
Contoh DFA lainnya :
Nondeterministic
Finite Automata
*
Perbedaan dengan NFA: fungsi transisi dapat memiliki 0 atau lebih fungsi
transisi.
¨
G = ({q0 , q1 , q2
, q3, q4 }, {0,1}, d
, q0 , { q2 , q4}}
|
d
|
0
|
1
|
|
q0
|
{ q0,q3}
|
{q0,q1}
|
|
q1
|
e
|
{q2}
|
|
q2
|
{q2}
|
{q2}
|
|
q3
|
{q4}
|
e
|
|
q4
|
{q4}
|
{q4}
|
¨
String diterima NFA bila terdapat
suatu urutan transisi berdasar input, dari state awal ke state akhir.
¨
harus mencoba semua kemungkinan.
¨
Contoh : string 01001
Contoh
: FSA yang menerima bahasa {an | n³0 }
* Dua buah state dari FSA disebut
indistinguishable (tidak dapat dibedakan)
apabila :
d(q,w)ÎF sedangkan d(p,w)ÏF dan
d(q,w) ÏF sedangkan d(p,w) ÎF untuk semua w Î S*
* Dua buah state dari FSA
disebut distinguishable (dapat
dibedakan) bila terdapat w Î S*
sedemikian
hingga:
d(q,w)ÎF sedangkan d(p,w)ÏF dan
d(q,w) ÏF sedangkan d(p,w) ÎF untuk semua w Î S*
Prosedur menentukan
pasangan status indistinguishable sebagai berikut :
1. Hapus
semua state yang tak dapat dicapai dari state awal.
2. Catat
semua pasangan state (p,q) yang distinguishable, yaitu {(p,q) | p Î
F Ù
q Ï
F}.
3. Untuk
setiap pasangan (p,q) sisanya, untuk setiap aÎ S, tentukan d(p,a)
dan d(q,a).
Contoh :
1. Hapus
state yang tidak tercapai -> tidak ada.
2. Pasangan
distinguishable (q0,q4), (q1,q4),
(q2,q4), (q3,q4).
3. Pasangan
sisanya (q0,q1), (q0,q2), (q0,q3),
(q1,q2) (q1,q3) (q2,q3)
.
|
pasangan
|
state 1
|
state 2
|
Hasil
|
||
|
0
|
1
|
0
|
1
|
||
|
(q0,q1)
|
q1
|
q3
|
q2
|
q4
|
distinguishable
|
|
(q0,q2)
|
q1
|
q3
|
q1
|
q4
|
distinguishable
|
|
(q1,q2)
|
q2
|
q4
|
q1
|
q4
|
indistinguishable
|
|
(q0,q3)
|
q1
|
q3
|
q2
|
q4
|
distinguishable
|
|
(q1,q3)
|
q2
|
q4
|
q2
|
q4
|
indistinguishable
|
|
(q2,q3)
|
q1
|
q4
|
q2
|
q4
|
indistinguishable
|
Catatan : jumlah
pasangan seluruhnya :
Prosedur
Reduksi DFA sebagai berikut :
1. Tentukan
pasangan status indistinguishable.
2. Gabungkan
setiap group indistinguishable state ke dalam satu state dengan relasi
pembentukan group secara berantai : Jika p dan q indistingishable dan jika q
dan r indistinguishable maka p dan r indistinguishable, dan p,q serta r
indistinguishable semua berada dalam satu group.
3. Sesuaikan
transisi dari dan ke state-state gabungan.
Contoh
1. pasangan
status indistinguishable (q1,q2), (q1,q3) dan (q2,q3).
2. q1,q2,q3
ketiganya dapat digabung dalam satu state q123.
3. Menyesuaikan
transisi, sehingga DFA menjadi
3. Tata
Bahasa Bebas Konteks
3.1. Gambaran
Bahasa Bebas Konteks
Konsep Dasar
- Anggota
alfabet dinamakan simbol terminal.
- Kalimat
adalah deretan hingga simbol-simbol terminal.
- Bahasa
adalah himpunan kalimat-kalimat. Anggota bahasa bisa tak hingga kalimat.
- Simbol-simbol
berikut adalah simbol terminal :
ü huruf kecil, misalnya : a, b, c, 0, 1, …
ü simbol operator,
misalnya : +, -, dan ´
ü simbol tanda
baca, misalnya : (, ), dan ;
ü string yang
tercetak tebal, misalnya : if, then, dan else.
- Simbol-simbol
berikut adalah simbol non terminal
/Variabel :
ü huruf besar,
misalnya : A, B, C
ü huruf S sebagai simbol awal
ü string yang
tercetak miring, misalnya : expr .
- Huruf
yunani melambangkan string yang tersusun atas simbol-simbol terminal atau
simbol-simbol non terminal atau campuran keduanya, misalnya : a, b, dan g.
- Sebuah
produksi dilambangkan sebagai a ® b, artinya :
dalam sebuah derivasi dapat dilakukan penggantian simbol a dengan
simbol b.
- Derivasi
adalah proses pembentukan sebuah kalimat atau sentensial. Sebuah derivasi
dilambangkan sebagai : a Þ b.
- Sentensial
adalah string yang tersusun atas simbol-simbol terminal atau simbol-simbol
non terminal atau campuran keduanya.
- Kalimat
adalah string yang tersusun atas simbol-simbol terminal. Kalimat adalah
merupakan sentensial, sebaliknya belum tentu..
Deskripsi bahasa
alami :
<kalimat> ® <subjek>
<predikat>
<subjek> ® <kata benda>
<predikat> ® <kata kerja>
<kata benda> ® kucing
<kata kerja> ® berlari
<kata kerja> ® menyapu
Contoh :
·
kucing berlari.
·
kucing menyapu (sintaks yes,
semantik no).
Dalam tatabahasa
bebas konteks :
·
Ruas kiri dari aturan produksi terdiri dari satu simbol non terminal.
·
Ruas kanan dapat berupa string yang dibentuk dari simbol terminal dan
non terminal.
Contoh
S ®aSb | e
Kalimat-kalimat
yang dibangkitkan dari aturan produksi itu adalah e,ab,aabb,aaabbb,... , anbn
Contoh
A ®0A0
A ®1A1
A®a
Kalimat-kalimat yang dibangkitkan dari aturan
produksi itu adalah a,01a10, 1001a1001 , 110a011 babR
Contoh
:
S ® aSb | SS |e
Bahasa
yang dihasilkan oleh tatabahasa dengan aturan produksi di atas adalah :
L = {w Î (a + b)* |na(w)
=nb(w) }
3.2.
Leftmost dan Rightmost Derivation
Suatu penguraian /penurunan dikatakan leftmost derivation bila setiap tahapan penurunan variabel / non terminal
terkiri yang diuraikan. Apabila setiap tahapan penurunan variabel / non
terminal paling kanan yang diuraikan disebut rightmost derivation
Contoh
1 :
G=({A,B,S}, {a,b},S,P} dengan aturan produksi P :
S ® AB
A® aaA | l
B®Bb | l
Menspesifikasikan
bahasa :
L(G) = {a2nbm |
n³0 , m³0}
Leftmost
derivation untuk menghasilkan string aab
S Þ AB Þ aaAB Þ aaB Þ aaBb Þ aab
Righmost
derivation untuk menghasilkan string aab
S
Þ AB Þ ABb Þ aaABb ÞaaAb Þaab
Contoh
2 :
G=({A,B,S}, {a,b},S,P} dengan aturan produksi P :
S ® aAB
A® bBb
B® A | l
Leftmost
derivation untuk menghasilkan string abbbb
S Þ aAB Þ abBbB Þ abAbB Þ abbBbbB
Þ abbbbB Þ abbbb
Righmost
derivation untuk menghasilkan string abbbb
S Þ aAB Þ aA Þ abBb Þ abAb Þ abbBbb Þ abbbb
3.3.
Pohon Urai
Untuk menampilkan penguraian, dapat dilakukan dengan
membentuk pohon urai (sayangnya, urutan penguraian tidak terlihat).
Contoh :
3.4.
Parsing dan Keanggotaan
Untuk menentukan apakah string w berada di L(G),
dengan cara secara sistematis membangun semua kemungkinan penurunan, dan
mencocokkan hasilnya apakah ada yang sama dengan string w. (disebut exhaustive search parsing)
Contoh
:
Menentukan apakah string ab berada pada bahasa yang
dibentuk oleh grammar dengan aturan produksi S ® SS | aSb | bSa | l.
Untuk
penguraian pertama :
1. S Þ SS
2. S Þ aSb
3. S Þ bSa
4. S Þ l
Penguraian nomor 3 dan 4 tidak perlu dilanjutkan.
Penguraian 1 dan Penguraian 2 terbentuk sebagai berikut :
1a.
S Þ SS Þ SSS 2a. S Þ aSb Þ aSSb
1b.
S Þ SS Þ aSbS 2b. S
Þ aSb Þ aaSbb
1c.
S Þ SS Þ bSaS 2c. S Þ aSb Þ abSab
1d.
S Þ SS Þ S 2d. S Þ aSb Þ ab
3.5.
Ambiguitas pada Tatabahasa dan Bahasa
Tatabahasa bebas konteks G disebut ambigu
jika terdapat beberapa w Î L(G) yang mempunyai paling
sedikit dua buah pohon penurunan
Contoh
:
Tatabahasa
dengan aturan produksi S ® SS | aSb | l.
string
aabb mempunyai 2 pohon penurunan :
3.6.
Pumping Lemma untuk bahasa bebas konteks
¨
Jika suatu rangkaian simbol / string yang cukup panjang yang merupakan
sebuah bahasa bebas konteks, maka kita dapat menemukan dua substring yang
jaraknya berdekatan yang jika dipompa, string baru yang diperoleh merupakan
bahasa bebas konteks juga.
¨
Secara formal, lemma di atas dinyatakan dengan
¨
Syarat “ kedua lokasi berdekatan” dinyatakan dengan kondisi |vwx| £ n.
¨
Jika salah satu v atau x diambil sebagai string kosong, maka lemma
diatas berubah menjadi lemma untuk bahasa reguler
Contoh :
Tatabahasa
dengan aturan produksi
S ®uAy
A ® vAx
A ® w
maka aturan derivasinya sebagai berikut :
S Þ uAy Þ uwy
S Þ uAy Þ uvAxy Þuvwxy
S Þ uAy Þ uvAxy Þ uvvAxxy Þuvvwxxy
sehingga
untuk setiap i ³0 , uviwxiy
Î L.
3.7.
Sifat sifat tertutup bahasa bebas konteks
¨
Gabungan dua CFL merupakan CFL juga.
Jika
diketahui dua buah CFG G1= (N1,T1,S1,P1)
dan G2=(N2,T2,S2,P2)
yang menghasilkan bahasa L1 dan L2 , maka CFG L1 È
L2 dapat dibentuk dengan cara :
1.
Menggabungkan
kedua himpunan dan menambahkan satu simbol variabel baru S
2.
Menggabungkan
kedua himpunan simbol terminal
3.
Menggabungkan
kedua himpunan aturan produksi dan menambahkan satu aturan produksi baru
S ® S1|S2
yang digunakan untuk memilih salah satu simbol awal S1 atau S2
dari simbol awal baru S
G3
= (N1ÈN2È{S},T1ÈT2
,S,P1ÈP2 È{S®S1|S2}}
¨
Penyambungan
dua CFL merupakan CFL juga.
Jika diketahui dua buah
CFG G1= (N1,T1,S1,P1)
dan G2=(N2,T2,S2,P2)
yang menghasilkan bahasa L1 dan L2 , maka bahasa L1L2 dapat
dibentuk oleh :
G4
= (N1ÈN2È{S},T1ÈT2
,S,P1ÈP2 È{S®S1S2}}
¨
Klosure
Kleene dari CFL adalah CFL juga.
Klosure
Kleene dari tatabahasa G=(N,T,S1,P) adalah
G5
= (N È
{S} , T , S , P È {S ® S1S
| e
} )
¨
Bahasa
bebas konteks tertutup terhadap substitusi
Contoh
:
La
= {0 n1n | n ³1 } dan Lb
= { wwR | w Î (0+2)* }
dihasilkan
oleh tatabahasa Ga dengan aturan produksi
Sa ®
0Sa1 | 01 serta tatabahasa G2 dengan aturan produksi Sb ®
0Sb0 | 2Sb2 | e.
Didefinisikan
tatabahasa G dengan aturan produksi S ® aSbS | bSaS | e
Jika f adalah
substitusi f(a)= La dan f(b) = Lb maka f(L) adalah bahasa yang dihasilkan oleh
tatabahasa dengan aturan produksi :
S ® SaSSbS | SbSSaS
| e
Sa
® 0Sa1 | 01
Sb
® 0Sb0 | 2Sb2 | e
Tatabahasa Bebas Konteks dan Bahasa Pemrograman
¨
Tatabahasa bebas konteks digunakan untuk
mendefinisikan sintaks bahasa pemrograman.
¨
Menggunakan notasi BNF (Backus-Naur Form).
¨
Variabel / non terminal : <...> .
¨
Terminal : tanpa tanda.
¨
¬
diganti dengan ::=
¨
Contoh :
Statement if
then else
< if_statement> ::= if <expression>
<then_clause>
<else_clause>
4. PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS
4.1. Tujuan
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:
- Penghilangan produksi useless ( tidak berguna ).
- Penghilangan produksi unit.
- Penghilangan produksi ε .
4.2. Penghilangan Produksi Useless
Di sini produksi useless didefinisikan sebagai :
·
Produksi yang memuat simbol 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 :
§
Aturan produksi A à
D, simbol variabel D tidak memiliki penurunan.
§
Aturan produksi C à
bb, Penurunan dari simbol S, dengan jalan manapun tidak akan pernah mencapai C.
§
Simbol variabel E tidak memiliki aturan produksi
yang menuju terminal.
§
Konsekuensi no (3) Aturan produksi B à E, simbol variabel E
tidak memiliki penurunan.
§
Produksi yang useless:
A à
D
C à
bb
E à
aEa
B à
E
Penyederhanaannya menjadi:
S à
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
Analisa :
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 tidak 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 :
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
Contoh 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.
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
C à
ef
D à
dd
Contoh :
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 :
S à
Cba | D
A à
bbC
B à
Sc | ddd
C à
eAn | f | C
D à
E | SABC
E à
gh
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
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 :
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 à
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.
5. BENTUK NORMAL CHOMSKY
5.1. Definisi Bentuk Normal Chomsky
Bentuk
normal Chomsky / Chomsky Normal Form (CNF) merupakan salah satu bentuk normal yang
sangat berguna untuk tata bahasa bebas konteks ( CFG ). Bentuk normal Chomsky dapat dibuat dari sebuah tata bahasa bebas
konteks yang telah mengalami penyederhanaan yaitu penghilangan produksi useless, unit, dan ε. Dengan kata lain,
suatu tata bahasa bebas konteks dapat dibuat menjadi bentuk normal Chomsky dengan syarat tata bahasa bebas konteks
tersebut:
·
Tidak memiliki produksi useless
·
Tidak memiliki produksi unit
·
Tidak memiliki produksi ε
Aturan produksi dalam bentuk normal Chomsky ruas kanannya tepat
berupa sebuah terminal atau dua variabel. Misal :
A à BC
A à b
B à a
C à BA | d
Pembentukan Bentuk Normal Chomsky
Langkah-langkah pembentukan bentuk normal Chomsky secara umum sebagai berikut:
·
Biarkan aturan produksi yang sudah dalam bentuk normal Chomsky .
·
Lakukan penggantian aturan produksi yang ruas
kanannya memuat simbol terminal dan panjang ruas kanan > 1.
·
Lakukan penggantian aturan produksi yang ruas
kanannya memuat > 2 simbol variabel.
·
Penggantian-penggantian tersebut bisa dilakukan
berkali-kali sampai akhirnya semua aturan produksi dalam bentuk normal Chomsky .
·
Selama dilakukan penggantian, kemungkinan kita
akan memperoleh aturan-aturan produksi baru, dan juga memunculkan simbol-simbol
variabel baru
Contoh, tata bahasa bebas konteks ( kita anggap tata
bahasa bebas konteks pada bab ini sudah mengalami penyederhanaan ) :
S à bA | aB
A à bAA | aS | a
B à
aBB | bS | b
Aturan
produksi yang sudah dalam bentuk
normal Chomsky :
A à a
B à
b
Dilakukan penggantian aturan produksi yang belum bentuk normal Chomsky (‘=>’ bisa
dibaca berubah menjadi) :
S à
bA => S à P1A
S à
aB => S à P1B
A à
bAA => S à P1AA
=> A à P1P3
A à aS => A à P2S
B à
aBB => B à P2BB
=> B à P2P4
B à
bS => B à P1S
Terbentuk aturan produksi dan simbol variabel baru :
P1 à
b
P2 à
a
P3 à
AA
P4 à
BB
Hasil akhir aturan produksi dalam bentuk
normal Chomsky :
A à a
B à b
S à P1A
S à P2B
A à P1P3
A à P2S
B à P2P4
B à P1S
P1 à b
P2 à a
P3 à AA
P4 à
BB
Contoh, tata
bahasa bebas konteks:
S à aB | CA
A à a | bc
B à BC | Ab
C à aB | b
Aturan
produksi yang sudah dalam bentuk normal
Chomsky :
S à CA
A à a
B à BC
C à b
Penggantian aturan produksi yang belum dalam bentuk normal Chomsky :
S à
aB => S à P1B
A à
bc => S à P2P3
B à
Ab => B à A
P2
C à
aB => C à P1B
Terbentuk aturan produksi dan simbol variabel baru :
P1 à
a
P2 à
b
P3 à
c
Hasil akhir
aturan produksi dalam bentuk
normal Chomsky :
S à CA
A à a
B à BC
C à b
S à P1B
S à P2P3
B à A P2
C à P1B
P1 à a
P2 à b
P3 à c
Contoh :
Tata bahasa bebas konteks :
S à aAB | ch | CD
A à dbE | eEC
B à ff | DD
C à ADB | aS
D à i
E à jD
Aturan produksi yang sudah dalam bentuk normal Chomsky :
S à CD
B à DD
D à i
Penggantian aturan produksi:
S à
aAB => S à P1P2
S à
ch => S à P3P4
A à
dbE => A à P5P6
A à
eEC => A à P8P9
B à
ff => B à P10P10
C à
ADB => C à
AP11
C à
aS => C à P1S
E à
jD => E à P12D
Terbentuk aturan produksi baru:
P1 à
a
P2 à
AB
P3 à
c
P4 à
h
P5 à
d
P6 à
P7E
P7 à
b
P8 à
e
P9 à
EC
P10 à
f
P11 à
DB
P12 à
j
Hasil akhir dalam bentuk
normal Chomsky:
S à CD
B à DD
D à i
D à i
S à P1P2
S à P3P4
A à P5P6
A à P8P9
B à P10P10
C à AP11
C à P1S
E à P12D
P1 à a
P2 à AB
P3 à c
P4 à h
P5 à d
P6 à P7E
P7 à b
P8 à e
P9 à EC
P10 à f
P11 à DB
P12 à j
4.2. Algoritma
CYK untuk Tata Bahasa Bebas Konteks
Algoritma
CYK merupakan algoritma parsing dan
keanggotaan ( membership) untuk tata
bahasa bebas konteks. Algortima ini diciptakan oleh J. Cocke, DH. Younger, dan T.
Kasami. Syarat untuk penggunaan
algortima ini adalah tata bahasa harus berada dalam bentuk normal Chomsky .
Obyektivitas dari algortima ini untuk menunjukkan apakah suatu string dapat diperoleh dari suatu tata
bahasa.
Algoritma CYK sebagai berikut:
begin
1)
for i:= 1 to n do
2)
Vi1 := {A| A à a aturan produksi dimana simbol ke- i adalah
a };
3)
for j:= 2 to n do
4)
for i:= 1
to (n-j+1) do
begin
5)
Vij:=Ø;
6)
for
k:=1 to (j – 1) do
7)
Vij:= Vij υ (
A | A à BC adalah suatu
produksi, dimana B di Vik dan C di Vi+k,j-k }
end
end
Penjelasan:
·
n
= panjang untai yang akan diperiksa, missal : untuk
untai ‘ada’, n = | ada | =3
·
i akan menyatakan kolom ke-
·
j
akan
menyatakan baris ke-
·
tahapan no (1) dan (2) untuk
mengisi table baris pertama kolom 1 – n
·
no (3), interasi dari baris ke- 2 sampai n
·
no (4), interasi untuk mengisi
kolom 1 sampai ( n – baris + 1) pada suatu baris.
·
no (5) inisialisasi Vij dengan
Ø
·
no (6) dan no (7), interasi untuk memeriksa
mana saja yang menjadi anggota Vij
6.
PENGHILANGAN REKURSIF KIRI
6.1. 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.
Keterangan :
β=(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,
Contoh :
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.
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.
6.2. Tahapan Penghilangan Rekursif Kiri
Langkah-langkah
penghilangan rekursif kiri sebagai berikut :
§
Pisahkan aturan produksi yang
rekursif kiri dan yang tidak, missal :
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:
ü
A
à β1Z
| β2Z | .... βmZ
ü
Z
à α1 | α2 | α3 | .... αn
ü
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 produksi semula
yang tidak rekursif kiri.
Contoh :
Ttata bahasa bebas konteks :
S à
Sab | aSc |dd | ff | Sbd
Pertama-tama kita lakukan
pemisahan aturan produksi
Aturan produksi yang rekursif
kiri : S à
Sab | Sbd
Dari situ kita tentukan :
Untuk simbol ruas kiri sebagai
berikut S : α1 = ab, α2 = bd
Aturan produksi yang tidak
rekursif kiri : S à
aSc | dd | ff
Dari situ kita dapatkan:
Untuk simbol ruas kiri sebagai
berikut : S : β1 = aSc, β2 = dd, β3 = ff
Kita lakukan penggantian aturan
produksi yang rekursif kiri:
Untuk yang memiliki simbol ruas
kiri S:
S à
Sab | Sbd, digantikan oleh:
S à aScZ1 | dd Z1
| ffZ1
Z1 à ab | bd
Z1 à abZ1 | bd Z1
Hasil akhir setelah penghilangan rekursif kiri
adalah:
S à aSc | dd | ff
S à aScZ1 | dd
Z1 | ffZ1
Z1 à ab | bd
Z1 à abZ1 | bd Z1
Pada kasus di atas S adalah
satu-satunya simbol variabel yang menghasilkan produksi rekursif kiri.
Contoh lain, terdapat tata bahasa
bebas konteks:
S à Sab | Sb | cA
A à Aa | a | bd
Pertama-tama kita lakukan
pemisahan aturan produksi
Aturan produksi yang rekursif
kiri :
S à Sab | Sb
A à Aa
Dari situ kita tentukan:
Untuk simbol ruas kiri S: α1=
ab, α2 =b
Untuk simbol ruas kiri A: α1
= a
Aturan produksi yang tidak
rekursif kiri :
S à
cA
A à
a | bd
Dari situ kita dapatkan
Untuk simbol ruas kiri S: β1
= cA
Untuk simbol ruas kiri A: β1 = a, β2 =
bd
Kita lakukan penggantian aturan
produksi yang rekursif kiri:
Untuk yang memiliki simbol ruas
kiri S :
S à
Sab | Sb, digantikan oleh :
S à
cAZ1
Z1 à ab | b
Z1
à abZ1 |
bZ1
Untuk yang memiliki simbol ruas kiri A :
A à
Aa, digantikan oleh:
A à
a Z2 | bdZ2
Z2 à
a
Z2 à
a Z2
Hasil akhir setelah
penghilangan rekursif kiri adalah:
S à cA
A à a | bd
S à cAZ1
Z1 à ab | b
Z1 à abZ1 | bZ1
A à a Z2 | bdZ2
Z2 à a
Z2 à a Z2
Perhatikan
bahwa penghilangan rekursif kiri memunculkan simbol variabel baru, dan aturan
produksi baru yang rekursif kanan.
Contoh
lain, terdapat tata bahasa bebas konteks:
S à
Sa |aAc | c | ε
A à
Ab | ba
Pertama-tama
kita lakukan pemisahan aturan produksi
Aturan
produksi yang rekursif kiri:
S à
Sa
A à
Ab
Dari
situ kita tentukan:
Untuk
simbol ruas kiri S: α1 = a
Untuk
simbol ruas kiri A: α1 = b
Aturan
produksi yang tidak rekursif kiri:
S à
aAc | c | ε
A à
ba
Dari
situ kita dapatkan
untuk
simbol ruas kiri S:β1 = aAc, β2= c, β3 = ε
untuk
simbol ruas kiri A: β1 = ba
Perhatikan
produksi ε termasuk produksi yang tidak rekursif kiri
Kita
lakukan penggantian aturan produksi yang rekursif kiri :
Untuk
yang memilki simbol ruas kiri S :
S
à Sa, digantikan
oleh :
S à
aAcZ1 | cZ1 | Z1
Z1 à
a
Z1 à
a Z1
Untuk
yang memiliki simbol ruas kiri A:
A
à Ab, digantikan
oleh :
A à
ba Z2
Z2 à
b
Z2 à
bZ2
Hasil akhir setelah penghilangan
rekursif kiri adalah:
S à
aAc | c | ε
S à
aAcZ1 | cZ1 | Z1
A à
ba
A à
ba Z2
Z1 à a
Z1 à a Z1
Z2 à b
Z2 à b Z2
7. BENTUK NORMAL GREIBACH
7.1. Definisi Bentuk Normal Greibach
Bentuk normal Greibach
merupakan bentuk normal yang
memiliki banyak konsekuensi teoritis dan prkatis. Dalam bentuk normal Greibach kita membatasi posisi munculnya
terminal-terminal dan variabel-variabel. Suatu tata bahasa bebas konteks (CFG)
dikatakan dalam bentuk normal Greibach
/ Greibach Normal Form, selanjutnya kita sebut sebagai GNF, jika
setiap aturan produksinya ada dalam bentuk:
A à aα
Keterangan :
A : simbol terminal (tunggal), a ε T
Α : rangkaian simbol-simbol variabel (V*)
Atau dengan kata lain, suatu tata bahasa bebas
konteks dalam bentuk normal Greibach bila hasil produksinya (ruas kanan)
diawali dengan satu simbol terminal, slanjutnya bisa diikuti oleh rangkaian
simbol variabel. Contoh tata bahasa bebas konteks dalam bentuk bentuk normal Greibach:
S à
a | aAB
A à aB
B à cS
Untuk dapat diubah ke dalam bentuk
normaol Greibach, tata bahasa semula haru memenuhi syarat:
- Sudah dalam bentuk normal Chomsky
- Tidak bersifat rekursif kiri
- Tidak menghasilkan ε
Terdapat
dua cara pembentukan bentuk normal Greibach , yaitu melalui substitusi
dan perkalian matriks. Pada bagian berikutnya kita membahasa kedua cara
tersebut.
7.2.
Pembentukan Bentuk Normal Greibach dengan Substitusi
Secara
umum langkah-langkah untuk mendapatkan bentuk normal Greibach :
1.
Tentukan urutan simbol-simbol
variabel yang ada dalam tata bahasa. Misalkan terdapat m variabel dengan
urutan A1, A2, ...., Am
2.
Berdasarkan urutan simbol yang
ditetapkan pada langkah (1) seluruh aturan produksi yang ruas kanannya diawali
dengan simbol variabel dapat dituliskan dalam bentuk Ah à
Ai γ di mana h <> i (rekrusif kiri sudah dihilangkan),
γ bisa berupa simbol-simbol variabel :
a.
Jika
h < i, aturan produksu ini sudah benar ( tidakperlu diubah)
b.
Jika
h > i, aturan produksi belum benar. Lakukan substitusi
berulang-ulang terhadap Ai (ganti Ai pada produksi ini
dengan ruas kanan produksi dari variabel Ai ) sehingga suatu saat
diperoleh produksi dalam bentuk Ah à Ap γ (dimana h
£ p )
i)
Jika
h = p , lakukan penghilangan rekursif kiri
ii)
Jika h < p, aturan produksi
sudah benar
3.
Jika
terjadi penghilangan rekursif kiri pada tahap (2b), sejumlah simbol variabel
baru yang muncul dari operasi ini dapat disisipkan pada urutan variabelsemula
dimana saja asalkan ditempatkan tidak sebelum Ah (di kiri)
4.
Setelah
langkah (2) & (3) dikerjakan maka aturan-aturan produksi yang ruas kanannya
dimulai simbol variabel sudah berada dalam urutan yang benar
Ax
à
Ay g
( di mana x < y )
Produksi-produksi
yang lain ada dalam bentuk:
Ax
à
a g
( a = simbol terminal )
Bx
à
g
(
B2 = simbol variabel baru yang akan muncul sebagai akibat dari
operasi penghilangan rekursif kiri ).
5.
Bentuk normal Greibach diperoleh dengan cara melakukan substitusi
mundur mulai dari variabel Am, lalu Am-1, Am-2,
..... Dengan cara ini aturan produksi dalam bentuk Ax à Ay g dapat diubah sehinga ruas
kanannya dimulai dengan simbol terminal.
6.
Produksi
dalam bentuk Bx à g juga dapat diubah dengan cara
substitusi seperti pada langkah (5).
Contoh (tata bahasa
bebas konteks sudah dalam bentuk normal Chomsky dan memenuhi syarat
untuk diubah ke bentuk normal Greibach), simbol awal adalah S:
S à
CA
A à
a | d
B à
b
C à
DD
D à
AB
Kita tentukan urutan
simbol variabel, misalnya S, A, B, C, D (S<A<B<C<D).
* Perhatikan urutan
tersebut boleh anda tentukan sendiri, buatlah urutan sedemikian sehingga
memudahkan untuk proses selanjutnya
Kita periksa aturan
produksi yang simbol pertama pada ruas kanan adalah simbol variabel, apakah
sudah memenuhi ketentuan urutan variabel:
§ S à CA ( sudah memenuhi aturan
karena S<C)
§ C à DD (sudah memenuhi karena
C<D)
§ D à AB (tidak memenuhi, karena
D>A)
Yang belum memenuhi
urutan yang telah kita tentukan adalah: D à AB, karena ruas
kiri > simbol pertama pada ruas kanan. Maka kita lakukan sibstitusi pada
simbol variabel A, aturan produksi menjadi :
D
à
aB | dB
Setelah
semua aturan produksi sudah memenuhi ketentuan urutan variabel, kita lakukan
substitusi mundur pada aturan produksi yang belum dalam bentuk normal
Greibach (‘=>’ dibaca ‘menjadi’):
§ C à DD => C à aBD | dBD
§ S à CA => S à aBDA | dBDA
* Perhatikan substitusi
mundur dimulai dari aturan produksi yang memiliki ruas kiri dengan urutan
variabel paling akhir ( kasus di atas:S<A<B<C<D, maka C lebih dulu
disubstitusikan daripada S ).
Hasil akhir aturan
produksi yang sudah dalam bentuk normal Greibach :
S à
aBDA | dBDA
A à
a | d
B à
b
C à
aBD | dBD
D à
aB | dB
* Perhatikan : setiap
substitusi kita lakukan pada simbol variabel pertamapada ruas kanan ( pada
aturan produksi yang belum bentuk normal Greibach tentunya ).
Prinsipnya
:
- Biarkan
aturan produksi yang sudah dalam bentuk normal Greibach
- Tentukan
pengurutan simbol variabel, berdasarkan kondisi aturan produksi yang ada
buatlah urutan sedemikian sehingga memudahkan untuk proses selanjutnya.
Mulailah terlebih dahulu dari seimbol awal.
§
Lakukan
perubahan pada aturan produksi yang belum memenuhi ketentuan urutan tersebut
dan bila perlu selama proses itu bisa dilakukan substitusi dan penghilangan
rekursif kiri.
- Lakukan
substitusi mundur sedemikian rupa sehingga semua aturan produksi akan
diawali dengan tepat sebuah simbol terminal. Proses substitusi mundur
dimulai dari aturan produksi dengan urutan paling akhir.
- Lakukan
substitusi mundur juga pada aturan produksi baru yang muncul sebagai hasil
penghilangan rekursif kiri.
Contoh (simbol awal A) :
A à
BC
B à
CA | b
C à
AB | a
Kita tentukan urutan
simbol: A,B,C ( A<B<C )
A à
BC ( sudah memenuhi karena A<B)
B à
CA (sudah memenuhi karena B<C)
C à
AB (padahal C > A sehingga harus diubah)
Pengubahan C à
AB:
C à
AB => C à
BCB => C à
CACB | bCB
Untuk C à
CACB lakukan penghilangan rekursif kiri menjadi
C
à bCBZ1 | aZ1
Z1
à ACB
Z1
à ACBZ1
Kita lihat seluruh
hasil produksi dari variabel C, sudah dalam bentuk normal Greibach:
C à
bCBZ1 | aZ1 | bCB | a
Setelah semua aturan
produksi sudah memenuhi ketentuan urutan variabel, kita laukan substitusi
mundur:
B à
CA => B à
bCBZ1A | aZ1A | bCBA | aA
A à
BC => A à
bCBZ1AC | aZ1AC | bCBAC | aAC | bC
Selanjutnya lakukan
pula substitusi pada aturan produksi dengan variabel baru yang terbentuk (pada contoh
ini Z1) :
§ Z1 à ACB => Z1 à bCBZ1ACCB | aZ1ACCB
| bCBACCB | aACCB | bCCB
§ Z1 à ACBZ1 => Z1
à bCBZ1ACCBZ1
| aZ1ACCBZ1 | bCBACCBZ1 | aACCBZ1 |
bCCBZ1
Hasil akhir aturan
produksi dalam bentuk bentuk normal Greibach :
A à
bCBZ1AC | aZ1AC | bCBAC | aAC | bC |
B à
bCBZ1A | aZ1A | bCBA | aA | B
C à
bCBZ1 | aZ1 | bCB | a
Z1 à
bCBZ1ACCB | aZ1ACCB | bCBACCB | aACCB | bCCB
Z1 à
bCBZ1ACCBZ1 | aZ1ACCBZ1 | bCBACCBZ1
| aACCBZ1 | bCCBZ1
Sumber Pustaka :
Teori Bahasa dan
Otomata, Heru Cahya Rustamadji, Fakultas Teknik Industri Universitas
Pembangunan Nasional, 2004.
Computation Engineering
: Applied Automata Theory and Logic, Gopalakrishnan, Ganesh, New York :
Springer, 2006.
Introduction to
Automata Theory, Languages, and Computation, 2nd Edition, Hopcroft,
John E. et al, New York : Addison-Wesley, 2001.
Bermanfaat buat tugas saya gan