1 Contents FINITE STATE AUTOMATA (Otomata Hingga) ........................................................................................... 2 Deterministic/Non Deterministic Finite Automate ............................................................................... 2 Ekwivalensi DFA dan NFA..................................................................................................................... 4 Contex Free Grammer(CFG) ................................................................................................................. 8 Penyederhanaan CFG .......................................................................................................................... 9 Bentuk Normal Chomsky ................................................................................................................... 10 Penghilangan Rekursi Kiri ................................................................................................................... 11 Bentuk Normal GreinBach ................................................................................................................. 12 Gambar 1 Diagram DFA dan NFA ............................................................................................................. 2 Gambar 2 Contoh DFA ............................................................................................................................. 2 Gambar 3 DFA hasil rekonstrusi NFA........................................................................................................ 6 Gambar 4 Table DFA hasil rekonstruksi NFA ............................................................................................ 7 Gambar 5 Bukti Abiguitas ........................................................................................................................ 9 http://contoh.in
12
Embed
Contents - contoh.in 3 δ(q 0,a) = q 1 Dibaca q 0 diberi masukan a state berpindah ke q 1 δ(q 1,b) = q 2 q 2 adalah state akhir 3. Bagaimana mengubah fungsi transisi menjadi untai
This document is posted to help you gain knowledge. Please leave a comment to let me know what you think about it! Share it to your friends and learn new things together.
Transcript
1
Contents FINITE STATE AUTOMATA (Otomata Hingga) ........................................................................................... 2
Tatabahasa ini bersifat ambigu. Tunjukan secara khusus bahwa untai aab memiliki dua:
a. Pohon Urai
b. Derivasi terkiri
c. Derivasi terkanan
http://contoh.in
9
Jawab:
a.
b. S=>aS=> aaSbS=>aaεbε Derivasi terkiri
c. S=>aSbS=>aSbε=>aaSbε=> aaεbε Derivasi terkanan
Penyederhanaan CFG
11. Sederhanakanlah produksi berikut
S→aABc|CA|F A→Ab|a B→C|b C→D| ε D→dd Jawab:
- Hilangkan produksi useless: produksi yang tidak dapat menghasilkan terminal dan yang tidak
dapat dijangkau.
S→F Tidak dapat menghasilkan terminal
- Hilangkan produksi Unit
B→C; C→D telalu ber-tele2
- Hilangkan produksi
C →ε produksi C tidak dibutuhkan.
- Produksi yang sederhana
S→aABc|SA Untuk CA, karena C dihilangkan, maka C diganti produksi S yang menurunkan dd
S→dd
S b S a
S a
S
ε ε
S b S a
S
a S
ε
ε
Gambar 5 Bukti Abiguitas
http://contoh.in
10
A→Ab|a B→b|dd D→dd
Bentuk Normal Chomsky 12. Dari hasil konstruksi produksi jawaban soal no 11 buatlah bentuk normal chomskynya:
Jawab:
Bentuk normal chomsky mensyaratkan sudah dalam bentuk sederhana, posisi paling kiri pada
produksi harus terdiri dari minimal satu terminal dan atau dua variable
Dari jawaban produksi diatas sebagai berikut:
S→aABc|SA S→dd A→Ab|a B→b|dd D→dd
Atruran produksi yang sudah dalam bentuk normal:
S→SA A→a B→b Lakukan penggantian produksi yang belum membentuk normal chomsky
S→aABc=> P1ABc=>P1P2c=>P1P2P3 S→P4d A→AP5 B→P4d D→P4d Bentuk aturan produksi dengan simbol variable barunya P1→a P2→AB P3→c P4→d P5→b Bentuk Normal Chomsky
S→SA|P1P2P3 S→P4d A→AP5|a B→P4d|b D→P4d P1→a
http://contoh.in
11
P2→AB P3→c P4→d P5→b 13. Perhatikan produksi unit berikut
S→ASB|ε A→a B→SbS|A|bb Tentukan
- Simbol apa saja yang tidak berguna
- Hilangkan produksi ε
- Hilangkan produksi unit
- Buatlah bentuk normal chomsky
Penghilangan Rekursi Kiri
14. Perhatikan produksi unit berikut
S → SaA|Sbc|BC|Cd A→ a B→ b C→ c
- Sebutkan produksi unit mana saja yang rekursi kiri
- Hilangkan produksi unit yang rekursi kiri
Jawab:
- Produksi unit yang rekursi kiri
S→SaA|Sbc
Dari produksi tersebut ditentukan untuk simbol ruas kiri
S: α1=aA α2=bc
- Produksi unit yang tidak rekursi
S→BC|Cd
Dari produksi tersebut ditentukan
S: β1=SBC β2=Cd
- Lakukan penggantian aturan produksi yang rekursi kiri
http://contoh.in
12
S→BCZ1|CdZ1 Untuk tiap simbol yang tidak rekursi kiri yang merupakan hasil produksi
S ditambahkan simbol baru Z1
Z1→aA|bc Z1 menampung simbol2 yang ada pada produksi unit rekursi
Z1→aAZ1|bcZ1 Melampirkan Z1 pada sisi terkanan di simbol2 produksi yang rekursi
- Hasil akhir produksinya sebagai berikut
S→BC|Cd S→BCZ1|CdZ1 Z1→aA|bc Z1→aAZ1|bcZ1
Bentuk Normal GreinBach
15. Perhatikan produksi unit berikut
S→BC|AB A→a|b B→b|c C→BA
- Lakukan pengurutan terhadap simbol variable yang nampak
S<A<B<C
- Periksa produksi yang ruas paling kanannya simbol variable, cek apakah sudah memenuhi
urutan seperti tampak diatas
S→BC ok S→AB ok C→BA no
- Lakukan subtitusi terhadap produksi yang tidak memenuhi syarat berurut
C→BA => C→bA|cA Diambil dari simbol variable pertama saja
- Lakukan subtitusi mundur untuk simbol variable yang belum dalam bentuk normal