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
1 http://contoh.in
FINITE STATE AUTOMATA (Otomata Hingga) Deterministic/Non Deterministic Finite Automate 1. Sebutkan definisi formal Deterministic dan Non Deterministic State Automata Jawab: Automata yang dapat berpindah dari satu state (Titik tujuan tertentu) ke state tunggal lainnya setelah sebelumnya membaca sembarang simbol masukan. Istilah deterministik mengacu bahwa setiap simbol masukan hanya menuju pada satu dan hanya satu state tujuan. Sedangkan non deterministik mengacu pada untuk setiap simbol masukan terdapat kemungkinan lebih dari satu state tujuan. a
q0
q1
a
q0
q1
a q2 Gambar 1 Diagram DFA dan NFA
Notasi FSA:A= {Q, ∑, δ , S, F} Q = Himpunan sejumlah state ∑ = Himpunan simbol masukan δ = Fungsi transisi S = State Awal F =State Akhir
2. Jelaskan proses kerja dari FSA Jawab: FSA memutuskan apakah suatu untai simbol masukan(bahasa) dapat diterima atau tidak. Jika setiap simbol masukan diberikan dapat mencapai state akhir maka dikatakan untai simbol masukan tersebut dapat diterima.
q0
a
q1
b
q2
Gambar 2 Contoh DFA
Pada Diagram DFA, jika mesin otomata tersebut diberikan masukan untai simbol ω=ab dapat diterima karena untai tersebut berakhir pada state q2 Untuk membuktikannya berikut fungsi transisinya. 2 http://contoh.in
δ(q0,a) = q1
Dibaca q0 diberi masukan a state berpindah ke q1
δ(q1,b) = q2
q2 adalah state akhir
3. Bagaimana mengubah fungsi transisi menjadi untai atau disebut juga dengan extended transition function(fungsi transisi yang diperluas) pada DFA Jawab: Transisi yang diperluas adalah peristiwa yang terjadi pada saat berada disuatu sembarang state dan mengikuti suatu barisan masukan. Jika fungsi transisi δ maka fungsi transisi perluasan yang dibangun dari δ adalah . fungsi transisi yang diperluas adalah fungsi yang mengambil state q serta untai ω dan menghasilkan state p. Notasi: (q,ε) = q artinya jika berada disuatu state dan tidak ada masukan apapun maka akan tetap berada di state tersebut. Misalkan ω untai berbentuk xa maka a adalah simbol terakhir dan x adalah untai yang terdiri dari seluruh simbol kecualisimbol terakhir. Contoh ω = 1011 maka a = 1 dan x = 101 (dipecah menjadi dua bagian), maka (q, ω) = δ( (q,x),a) Artinya untuk mendapatkan (q, ω) terlebih dulu harus menghitung (q,x) . Contoh: jika terdapat ω = 110101, yang dimulai dari ε dan seterusnya. Buatlah fungsi transisinya. (q0, ε) = q0 (q0, 1) = δ( (q0, ε),1) = δ(q0,1) = q1 (q0, 11) = δ( (q0, 1),1) = δ(q1,1) = q0 (q0, 110) = δ( (q0, 11),0) = δ(q0,0) = q2
δ *→q0 q1 q2 q3
0 q2 q3 q0 q1
1 q1 q0 q3 q2
(q0, 1101) = δ( (q0, 110),1) = δ(q2,1) = q3 (q0, 11010) = δ( (q0, 1101),0) = δ(q3,0) = q1 (q0, 110101) = δ( (q0, 11010),1) = δ(q1,1) = q0
4. Sebutkan perbedaan antara DFA dengan NFA, yang mudah dikenali Jawab: 3 http://contoh.in
Perbedaan hanya pada setiap setiap arah state disajikan dalam bentuk himpunan, walau hanya memiliki satu anggoto saja. Perhatikan tabel transisi pada contoh berikut: Contoh: mesin atomata A= ({q0,q1,q2},{0,1}, δ,q0,{q2}) Δ q0 q1 q2
0 {q0,q1} φ φ
1 {q0} {q2} Φ
5. Jelaskan tentang perluasan fungsi transisi pada NFA Jawab: Notasi: (q,ε) = {q} artinya sama seperti penjelasan pada DFA, bedanya state tujuan digambarkan dalam bentuk himpunan. Anggap ω memiliki bentuk ω=xa, dimana a simbol terakhir ω dan x sisa dari ω. Anggap juga {p1, p2, p3, …pk} dengan rumusan sebagai berikut:
Contoh:
(q,x) =
0,1
q0
0
q1
1
qq22
Jika pada diagram tersebut kita masukan ω = 00101 maka fungsi perluasan transisinya sebagai berikut:
Diurai dibawah hasil uraian dicocokan dengan diagram Untuk langkah berikutnya sama
Ekwivalensi DFA dan NFA 6. Jelaskan apa yang disebut dengan Ekwivalensi DFA dan NFA 4 http://contoh.in
Jawab: Adanya anggapan bahwa bahasa yang dibentuk melalui NFA bisa disajikan dalam bentuk DFA. Hal ini dapat dilakukan dengan mengkonstruksi himpunan bagian: Konstruksi NFA Konstruksi DFA Sedemikian rupa sehingga L(N) = L(D) QD adalah himpunan bagian dari QN , ingat jika QN memiliki n state maka QD memiliki 2n state, kadang kala ada state yang tidak dapat diakses melalui QD, state ini harus dibuang. Sehingga banyaknya state dapat dikurangi. , berarti FD adalah seluruh FD adalah himpunan bagian S dari QN, sehingga himpunan state N yang memasukan setidaknya satu state penerima N. Untuk setiap himpunan dan untuk setiap simbol a pada ∑ berlaku,
Contoh: 0,1
q0
0
q1
qq22
1
Karena himpunan state N= 3 maka konstruksi himpunan bagian menghasilkan DFA dengan 23=8 Tabel hasil rekonstruksi dari diagram tersebut sebagai berikut: A B C D E F G H
Δ
0
1
→{q0} {q1} *{q2} {q0,q1} *{q0,q2} *{q1,q2} *{q0,q1,q2}
{q0,q1}
{q0} {q2}
{q0,q1} {q0,q1}
{q0, q2} {q0} {q2} {q0,q2}
{q0,q1}
-
Total terdapat 8 state → menandakan state awal * Menandakan state akhir Alphabet menandakan nama lain tiap state
5 http://contoh.in
Di mulai dari {q0} yang dapat ditransisikan ke dan karena ada pembentukan himpunan baru karenanya perlu dibuat fungsi transisinya dengan menambahkan state baru untuk himpunan tersebut.
Dari hasil fungsi transisi tersebut terbentuk graph baru sebagai berikut: 0 0 1 1
0 1 Gambar 3 DFA hasil rekonstrusi NFA
Kesimpulan DFA hasil rekonstruksi dari NFA diatas ekwivalen artinya dapat menerima masukan yang sama. 7. Ubah NFA berikut menjadi DFA a. Table transisi 1 0 →p {p,q} q {r} r {s} *s
1 {p} {r} {s}
6 http://contoh.in
0 →{p} {p,q} {q} {r} {r} {s} *{s} {p,q} {p,q,r} {p,r} {p,r,s} {p,q,r} {p,q,r,s} *{p,q,r,s} {p,q,r,s} *{p,r,s} {p,r,s}
1 {p} {r} {s} {p,r} {p} {p,r} {p,r,s} {p}
Gambar 4 Table DFA hasil rekonstruksi NFA
b. Tabel transisi 2 (Latihan Melengkapi) 0 →p {q,s} *q {r} r {s} *s
1 {q} {q,r} {p} {p}
c. Tabel transisi 3 (Latihan Melengkapi) 0 →p {p,q} q {r,s} r {p,r} *s *t
1 {p} {t} {t}
7 http://contoh.in
Contex Free Grammer(CFG) 8. Sebutkan 4 komponen penting dalam grammer (Tatabahasa) suatu bahasa Jawab: 1. Terdapat sejumlah hingga simbol dalam bentuk untai yang terdefinisi yang kita sebut terminal. Contoh: {0,1},{a, b, c, d}. 2. Terdapat himpunan hingga variable, sering disebut non-terminal. Masing-masing variable mewakili suatu bahasa yaitu himpunan untai. 3. Salah satu variable mewakili bahasa yang telah di definisikan yang disebut simbol variable awal. Variable lainnya mewakili kelas untai tambahan yang digunakan untuk membantu mendefinisikan bahasa simbol awal. 4. Terdapat himpunan hingga produksi atau aturan yang mewakili definisi rekursif mengenai bahasa. dimana V adalah Variable, T adalah Tata bahasa G didefinisikan sebagai Terminal, P adalah produksi dan S adalah Variable awal. 9. Tata bahasa berikut membangkitkan bahasa ekspresi regular 0*1(0+1)*: S→A1B A→0A|ε B→0B|1B|ε Tentukan Derivasi paling kanan(left most derivation) dari untai berikut: a. 00101 Left most derivasi artinya melakukan penurunan produksi mulai pada produksi palingkanan. S=>A1B=>0AA1B=>00AA1B=>00 ε ε1B=>00 10B=>00101B=>00101 ε b. 1001 c. 0011
10. Perhatikan tata bahasa S→aS|aSbS| ε Tatabahasa ini bersifat ambigu. Tunjukan secara khusus bahwa untai aab memiliki dua: a. Pohon Urai b. Derivasi terkiri c. Derivasi terkanan
8 http://contoh.in
Jawab: a.
S
S S
a a
a
S b S ε
S b S
a
ε
S
ε
ε
Gambar 5 Bukti Abiguitas
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
-
Hilangkan produksi Unit B→C; C→D
-
telalu ber-tele2
Hilangkan produksi C →ε
-
Tidak dapat menghasilkan terminal
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 9 http://contoh.in
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 10 http://contoh.in
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
11 http://contoh.in
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
-
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
-
S→BC => bC| cC S→AB => aB|bB Bentuk akhir Produksinya adalah S→ aB|bB S→bC|cC A→a|b B→b|c ;
C→bA|cA 12
http://contoh.in
