- Pada semua FSA yang sudah dipelajari, keputusannya terbatas pada diterima atau ditolak
- FSA tersebut biasa disebut sebagai accepter/finite state accepter
- Ada FSA yang dapat memiliki beberapa keluaran/ output,automata tersebut dikenal sebagai transducer
- Pada mesin moore output akan berasosiasi dengan state
- Mesin moore didefenisikan sebagai tuple:
M: (Q,Σ,δ,S,Δ,λ)
Q: Himpunan state
S: Himpunan symbol input
d: fungsi transisi
S: State awal,S ∈ Q
Δ: Himp Output
λ: Fungsi output untuk setiap state
- komponen final state (F) dihilangkan karena keputusan akhirnya berupa output yang dihasilkan
contoh:
Modulus (sisa pembagian) suatu bilangan input (dalam biner) dengan bilangan 3
Q : (q0,q1,q2)
Σ : [0,1] (input dalam biner)
Δ : [0,1,2] (hasil bilangan modulus 3=0 atau 1 atau 2)
S : q0
λ(q0) =0
λ(q1) =1
λ(q2) =2
- Input = 2 (10 biner), bila dimasukkan dalam mesin urutan statenya : q0,q1,q2. State akhir q2 maka λ(q2) =2 yang berarti 2 mod 3 = 2
- Input = 7 (111 biner), state = q0,q1,q0,q1. λ (q1)=1 berarti 7 mod 3 =1
- Input =12 (1100 biner), state = q0,q1, q0, q0, q0. λ (q0)=0 berarti 12 mod 3=0
mesin Mealy
- Output pada mesin mealy berasosiasi dengan transisi.
- Didefenisikan dengan 6 tuple:
M: (Q,S,d,S,?,?)
Q: Himpunan state
S: Himpunan symbol input
d: fungsi transisi
S : State awal,S ? Q
?: Himp Output
?: Fungsi output untuk setiap state
contoh :
sebuah mesin akan menerima (y) atau menolak (t) suatu masukan. Output Y akan dihasilkan jika string input memiliki akhiran 2 simbol yang sama secara berurutan.
Ekspresi regular : (0+1)*(00+11)
String yang diterima :00,11,000,011,100,111,….
Ekivalensi mesin moored an mesin mealy
? Untuk setiap mesin moore dapat dibuat mesin mealy yang ekivalen, demikian juga sebaliknya.
? Jumlah state pada mesin moore yang terbentuk = jumlah state pada mesin mealy X banyaknya output.
? Contoh :
Mesin moore yang ekivalen dengan mesin mealy yang lalu (mesin mealy pada kuliah sebelumnya)
Mesin mealy : jml state = 3 (q0,q1,q2)
Jumlah output =2 (Y,T)
Jml state mesin moore ekivalennya =3X2 =6
M: (Q,S,d,S,?,?)
Q: {q0Y,q1Y,q2Y,q0T,q1T,q2T}
S: {0,1}
S: {Y,T}
S:q0T
d (q0Y)=Y
d (q0T)=T
d (q1Y)=Y
d (q1T)=T
d (q2Y)=Y
d (q2T)=T
? Dari gambar tersebut state q0Y dapat dihapus karena tidak ada busur yang mengarah ke state tersebut (state tidak akan pernah dicapai/dilewati).
? Mesin mealy dapat dibentuk dari mesin moore dengan cara menambahkan label output ke setiap transisi dan menghapus label output dari setiap state.
? Contoh :
Mesin mealy yang akan ekivalen dengan mesin moore pada kuliah sebelumnya.
M: (Q,S,d,S,?,?)
Q: {q0,q1,q2 }
S: {0,1}
S: {0,1,2}
S:q0
d (q0,0)=0
d (q0,1)=1
d (q1,0)=2
d (q1,1)=0
d (q2,0)=1
d (q2,1)=2
Latihan :
1. Buat mesin moore yang menerima input karakter ‘<’,’>’,’=’,’ ‘(spasi).Output ditentukan dari apakah yang diterima merupakan token lebih besar (tG-greater),lebih kecil(tL-less), sama dengan (tLE), tidak sama dengan (tNE).
S=(‘<’,’>’,’=’,’_’}
S={tG,tGE,tL,tLE,tE,tNE}
2. Ubah mesin moore soal no.1 mesin menjadi mesin mealy yang ekivalen
Jawaban :
1. Mesin moore
2. Mesin mealy ekivalennya
Context Free Grammar (CFG)
Sekarang kita beralih dari tata bahasa regular ke kelas bahasa yang lebih luas, yaitu Context Free Grammar (CFG/ tata bahasa bebas konteks/tipe 2).
CFG memegang peran yang penting dalam teknologi kompilatorsejak tahun 196-an.
CFG membantu mempermidah implementasi parser/syntax analyzer yang berfungsi untuk melakukan pengecekan struktur program.
Saat ini CFG juga digunakan untuk mendeskripsikan struktur / format dokumen-dokumen, diantaranya DTD (Document Type Defenition) dan XML(extensible markup language).
Pembahasan CFG akan meliputi : notasi CFG, parse tree, dan push down automata(PDA). Parse tree (pohon penurunan) adalah hasil dari parser untuk sebuah bahasa pemrograman yang memperlihatkan struktur dari program.
1. Notasi CFG
Tata bahasa CFG (sama dengan tata bahasa regular) didefenisikan dengan 4 tupel, yaitu G={V,T,P,S}:
V=himpunan symbol variable /nonterminal
T=himpunan symbol terminal
P=kumpulan aturan produksi
S=simbol awal
Batasan aturan produks a ßuntuk CFG :
a berupa sebuah symbol variable
ßtidak ada batasan
aturan produksi CFG seringkali mengandung rekursif (variable diruas kiri muncul lagi diruas kanannya).
2. Parse tree
Sebuah pohon (tree) adalah suatu graph terhubung tidak sirkuler, yang memiliki satu simpul (node/vertex) yang disebut akar (root) dan memiliki lintasan ke simpul-simpul lain.
Pohon penurunan (parse tree/ derivation tree)berguna untuk menggambarkan bagaimana memperoleh suatu string dengan cara menurunkan semua symbol-simbol variable menjadi simbol-simbol terminal.
Contoh :
Misalkan sebuah tata bahasa bebas konteks (CFG) memiliki aturan produksi :
S AB
A aA | a
B bB | b
Maka pohon penurunan untuk memperoleh string ‘aabbb’ adalah : symbol awal S akan menjadi akar (root_). Setiap kali penurunan dipilih aturan produksi yang menuju ke solusi. Simbol-simbol variable akan menjadi simpul-simpul yang mempunyai anak. Simpul-simpul yang tidak mempunyai anak akan menjadi symbol terminal atau £.
Proses penurunan bias dilakukan dengan cara:
• Penurunan terkiri (leftmost derivation) :symbol variable yang diproses terlebih dahulu.
• Penurunan terkanan (rightmost derivation) :symbol variable terkanan yang diperoleh terlebih dahulu.
Misalkan sebuah tata bahasa bebas konteks (CFG) memiliki aturan produksi:
S aAS | a
A SbA | ba
Untuk memperoleh string aabbaa dari aturan produksi diatas:
• Dengan penurunan terkini : S => aAS => aSbAS => aabAS =>aabbaS =.aabbaa
• Dengan penurunan terkanan : S => aAS => aAa => aSbAa => aSbbaa =>aabbaa
Meskipun proses penurunannya berbeda tetapi pohon penurunannya tetap sama:
3. Ambiguitas
Ambiguitas terjadi jika terdapat lebih dari satu pohon penurunan yang berbeda untuk memperoleh suatu string.
Misalkan sebuah tata bahasa bebas konteks (CFG) memiliki aturan produksi:
S SbS | ScS | a
Terdapat dua cara untuk menurunkan string ‘abaca’;
• S => SbS =>SbScS =>SbSca =>Sbaca =>abaca
• S => ScS =>SbScS =>abScS =>abacS =>abaca
Yang menghasilkan pohon penurunan yang berbeda:
Push Down Automata (PDA)
Push down automata merupakan mesin automata untuk bahas bebas konteks (Context Free Language). PDA merupakan suatu NFA dengan transisi £ yang memilik stack (tumpukan). Operasi push dan pop data dilakukan pada puncak stack (top of stack). Pada stack berlaku model pengaksesan LIFO (Last In First Out).
Terdapat dua jenis PDA:
1. PDA final state: bahasa yang diterima adalah semua string input yang menyebabkan PDA mencapai final state (state akhir).
2. PDA empty (null) stack : bahasa yang diterima adalah semua string input yang urutan pergerakannya menyebabkan PDA mengosongkan stack.
Untuk suatu tata bahasa bebas konteks (CFG) dapat dibuat PDAnya, demikian juga sebaliknya.
1. Defenisi Formal PDA
Sebuah PDA dinyatakan dalam 7 tuple M={Q,?,+,d,S,Z,F} yaitu:
Q=himpunan state
?=himpunan symbol input
+=himpunan symbol stack
d =fungsi transisi
S=state awal, S € Q
Z= symbol awal stack, Z € +
F= final state, F € Q
Fungsi transisi d memiliki tiga argumen d(q,a,X), dimana :
q : state pada saat itu
a : symbol input , atau £
X : symbol pada stack
Dan output berupa pasangan (p,y), dimana:
P : state yang baru
y(gamma): string dari symbol-simbol stack yang maenggantikan X pada top of stack.
Maka fungsi transisi yang dapat dipilih pada suatu saat tergantung dari state, symbol input, dan symbol pada top of stack. Sebuah PDA, ketika menerima input selain dapat berpindah state juga dapat melakukan operasi pada state. Penggantian symbol pada top of stack pada suatu saat dengan operasi push dapat memasukkan satu atau lebih symbol.
2. PDA untuk suatu tata bahasa bebas konteks (CFG)
Ketika membuat PDA untuk suatu CFG, langah-langkahnya :
Defenisikan tuplenya:
Q= {q1,q2,q3}
?=symbol-simbol terminal( symbol input)
+= semua symbol variable,symbol terminal, dan symbol awal stack(Z)
S=q1
Z= Z
F= {q3}
Mesin dimulai dengan men-push Z pada top of stack, kemudian pada setiap langkah berikutnya lakukan salah satu hal berikut:
• Jika symbol pada top of stack berupa variable (misal A), gantilah dengan ruas kanan dari aturan produksi A(missal A -> W), maka kita ganti dengan w.
• Jika symbol pada top of stack berupa symbol terminal yang sama dengan symbol input berikutnya, maka symbol berikut di pop, dan input bergeser ke symbol berikutnya.
Berdasarkan aturan diatas, kita dapat mengkonstruksi empat jenis transisi:
1. d (q1,£,Z) = {(q2,SZ)}, untuk mempush symbol awal (S) ke stack.
2. d (q2, £,A) = {(q2,w) | A -> w adalah aturan produksi pada CFG tersebut}, buat untuk semua variable pada aturan produksi.
3. d (q2,a,a) = {(q2, £)} untuk setiap symbol terminal, yaitu untuk mem pop symbol terminal yang sama dengan input.
4. d (q2, £,Z) = {{q3,Z)}, jika selesai membaca input dan top of stack adlah Z, berarti string inpit sukses diterima oleh PDA, karena q3 adalah state akhir.
Contoh:
Misalkan sebuah CFG memiliki aturan produksi:
S aBc | Bac
B b | c
Maka dapat dibuat PDA-nya:
Q= {q1,q2,q3}
?= {a,b,c}
+= {S,B,a,b,c,Z}
S=q1
Z= Z
F= {q3}
Fungsi transisinya:
d (q1,£,Z) = {{q2,SZ)}
d (q2,£,S) = {{q2,aBc),(q2,Bac)}
d (q2,£,B) = {{q2,b),(q2,c)}
d (q2,a,a) = d {{q2,b,b)= d (q2,c,c) = {{q2, £)}
d (q2,£,Z) = {{q3,Z)}
berdasrkan aturan produksi, tata bahasa tersebut dapat menurunkan string ‘acc’:
S => aBc => acc
Langkah-langkah pada PDA ketika menerima string tersebut adalah sebagai berikut:
Z
1. konfigurasi awal mesin : state q1, tanpa menerima input (£), top of stack Z
fungsi transisi : d (q1,£,Z) = {{q2,SZ)}
Konfigurasi mesin menjadi: state q2, S di push
S
Z
2. input : tanpa menerima input (£)
fungsi transisi : d (q2,£,S) = {{q2,aBc) }
konfigurasi mesin menjadi : state q2, pop top of stack, push ‘aBc’
a
B
c
Z
3. input : menerima input ‘a’
fungsi transisi : d (q2,a,a) = {{q2, £) }
konfigurasi mesin menjadi : state q2, pop top of stack
B
c
Z
4. input : tanpa menerima input (£)
fungsi transisi : d (q2, £,B) = {{q2, c) }
konfigurasi mesin menjadi : state q2, pop top of stack, push ‘c’
c
c
Z
5. input : menerima input ‘c’
fungsi transisi : d (q2,c,c) = {{q2, £) }
konfigurasi mesin menjadi : state q2, pop top of stack
c
Z
6. input : menerima input ‘c’
fungsi transisi : d (q2,c,c) = {{q2, £) }
konfigurasi mesin menjadi : state q2, pop top of stack
Z
7. input : tanpa menerima input (£)
fungsi transisi : d (q2, £,Z) = {{q3, Z) }
konfigurasi mesin menjadi : state q3
tidak ada transisi lagi dari q3, karena sudah mencapai state akhir dan string input selesai dibaca, maka string ‘acc’ diterima oleh PDA tersebut.
Seperti terlihat pada deskripsi dari contoh diatas, didalam PDA bentuk penggambaran automatanya sendiri diangggap tidak terlalu penting. Jika diperlukan PDA dapat digambarkan sebagai diagram transisi yang umun:
Dari diagram transisi tersebut terlihat bahwa q1 berfungsi sebagai state awal, q3 sebagai final state, dan sebagai transisi lainnya terjadi pada state q2.
3. Deskripsi seketika (Instantaneous descriptions) pada DPA
Deskripsi seketika digunakan untuk menyatakan konfigurasi mesin PDA pada suatu saat secara formal. Perubahan dari satu kondisi ke kondisi berikutnya dipisahkan dengan tanda ‘|-‘ . konfigurasi suatu saat dinyatakan dengan (q,w,u), dimana q menyatakan state, w string yang belum dibaca, isi stack dimana symbol terkiri menyatakan top of stack. Tahapan pada contoh diatas dapat dituliskan dengan deskrisi seketika :
(q1, acc,Z) | - (q2,acc,SZ) | - (q2, acc,aBcZ) } | – (q2,cc,BcZ) | - (q2,cc,ccZ) | - (q2,c,cZ) | - (q3,£,Z) | - (q3, £,Z)
PENGHILANGAN REKURSIF KIRI
Langkah-langkah penghilangan rekursif kiri:
• Pisahkan aturan produksi yang rekursif kiri dan yang tidak, misal: Aturan produksi yang rekursif kiri:
A Aa1 | Aa2 | Aa3 | ....... Aan
Aturan produksi yang tidak rekursif kiri (termasuk produksi e):
A ß1 | ß2 | ß3 | ........ ßm
• Dari situ kita bisa tentukan a1, a2, .... an, 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 a1 | a2 | a3 | .... an
3) Z a1Z | a2Z | a3Z | .... anZ
• Hasil akhir berupa aturan produksi pengganti ditambah dengan aturan produksi
semula yang tidak rekursif kiri.
Contoh lakukan penghilangan produksi yang rekursif kiri dari CFG
S Sab | aSc | dd | ff | Sbd
Jawab : produksi rekusif kiri
S Sab | Sbd , a1=ab, a2=bd
Produksi yang tidak rekursif kiri
S aSc | dd | ff , ß1=aSc, ß2=dd, ß3=ff
Penggantian produksi rekursif kiri:
1. S aScZ | dd Z | ffZ
2. Z ab | bd
3. Z abZ | bd Z
Hasil akhir CFG:
S aSc | dd | ff
S aScZ | dd Z | ffZ
Z ab | bd
Z abZ | bd Z
*Pada kasus diatas 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: a1= ab, a2 =b
Untuk simbol ruas kiri A: a1 = 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:
i. S cAZ1
ii. Z1 ab | b
iii. Z1 abZ1 | bZ1
Untuk yang memiliki simbol ruas kiri A :
A Aa, digantikan oleh:
i. A a Z2 | bdZ2
ii. Z2 a
iii. 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.
BENTUK NORMAL GREIBACH
Pengerian 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 aa
a:simbol terminal (tunggal), a e T
a: 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 e
Terdapat dua cara pembentukan bentuk normal Greibach , yaitu melalui substitusi
dan perkalian matriks. Pada bagian berikutnya kita membahasa kedua cara tersebut.
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 ?
dimana h <> i (rekrusif kiri sudah dihilangkan), ? bisa berupa simbol-simbol
variabel
a. 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 < a =" simbol" b2 =" simbol">
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
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
