buatkan DFA untuk alfabet biner dengan spesifikasi bahasa adalah sebagai berikut :
1. mengenai kemunculan 1 adalah genap, sekaligus kemunculan 0 adalah genap. contoh strkosong, 0011, 00, 11, 1100, 110000 dlsb
2. mengenali string yang selalu diakhiri 10
3. mengenali string yang selalu diawali 01
4. mengenali string yang diawali 01 sekaligus diakhiri 10. contoh 010, 0110, 0101000010, dlsb
materi dapat diambil di sini : cs3113 17 Combining Mesin Turing
Kita bisa membangun suatu mesin turing menjadi bentuk yang lebih besar. Hal ini sebenarnya sama dengan penggabungan sub modul pada saat kita membangun program yang lebih besar. Untuk melakukannya, mesin turing akan ditransisikan sebagai suatu diagram transisi, dan kita bisa mengkombinasikannya sebagaimana operasi union, atau konkatenasi pada FA
Bayangkan kita memiliki mesin turing M1 dan M2, serta diagram transisi T1 dan T2 serta tape symbol, Dan kita ingin membangun suatu mesin turing yang lebih besar dengan melanjutkan melaksanakan M2 pada saat mesin kita selesai mengerjakan M1. Maka untuk operasi ini kita bisa bangun dengan menghilangkan halt state pada M1, dan menghilangkan initial state pada M2. Kemudian untuk menggabungkan mesin itu, untuk setiap x di machine symbol akan kita buatkan busur berlabel x/x dari old halt state M1 ke old initial state di M2.
operasi-operasi yang lain beserta contohnya dapat dilihat di slide.
Materi dapat didownload di sini : cs3113 16 Mesin Turing
Di propose oleh Alan M. Turing tahun 1936. Perbandingan dengan mesin sebelumnya: Mirip dengan FA, karena ada mekanisme kontrol dan terdapat input tape. Perbedaan ada pada pergerakan head yang memungkinkan maju dan mundur. Perbedaan lain pada kemampuan membaca dan menulis pada tape.
pada mesin turing, ada beberapa kondisi yang menyebabkan mesin turing berhenti (Halt State, Abnormal Termination)
1. Halt state berarti mesin langsung berhenti, (selamat).
2. Abnormal termination mesin berhenti karena error tidak bisa bergerak ke arah kiri pada saat head sudah berada di left end.
3. Non terminating loop : kondisi mesin yang tidak pernah berhenti dikarenakan bergerak ke kanan terus menerus.
detail mengenai materi mesin turing bisa dilihat di slide.
file dapat didownload di sini : cs3113 14 Chomsky Normal Form
Ada suatu bentuk dari CFG yang disebut dengan Chomsky Normal Form. Bentuk ini memiliki struktur :
A -> BC atau
A -> a
Dengan A, B, C adalah variabel, dan a adalah terminal. Panjang variabel di betha harus tepat 2, dan terminal harus tepat 1
untuk mengubah CFG menjadi bentuk normal dilakukan dengan langkah :
Mengeliminasi produksi ε
Mengeliminasi produksi unit (bentuk A->B)
Mengeliminasi useless symbol
detail dari masing-masing langkah bisa dilihat di slide.
Materi dapat didownload di sini : cs3113 13 PDA Vs Context Free Grammer
Sehingga jika kita memiliki CFG : G, dan PDA : M, akan kita miliki
First : untuk setiap CFG : G akan ada PDA : M sehingga L(G) = L(M).
Second : untuk setiap PDA : M akan ada CFG : G sehingga L(M) = L(G).
hubungan pertama sudah dijelaskan pada slide sebelumnya. pada slide kali ini akan dibahas mengenai hubungan yang kedua. atau lebih tepatnya adalah konversi dari PDA ke CFG.
adapun langkah-langkahnya adalah sebagai berikut :
materi Context Free Grammer vs PDA bisa didapatkan di sini : cs3113 12 Context Free Grammer Vs PDA
Sebagaimana regular grammer, CFG akan menggenerate string melalui derivasi.
Parse Tree : pohon dimana node adalah terminal dan non terminal dari grammer, dimana root adalah starting symbol, dan anak dari setiap non terminal adalah simbol yang menggantikan non terminal itu.
Contoh :
S -> zMNz
M -> aMa
M -> z
N -> bNb
N -> z
Ada dua pendekatan yakni
Leftmost derivation
S -> zMNz -> zaMaNz -> zazaNz -> zazabNbz -> zazabzbz
Rightmost derivation
S -> zMNz -> zMbNbz -> zMbzbz -> zaMabzbz -> zazabzbz
pada slide akan dibahas banyak mengenai konversi dari CFG ke PDA.
Slide dapat ditemukan di sini : cs3113 08 Operasi FA dan Regular Expression
jika kita memiliki suatu mesin FA, maka kita bisa membuat mesin FA yang lebih besar dari mesin-mesin yang kita punya dengan mengoperasikan mesin-mesin itu. beberapa operasi yang dapat dilakukan adalah :
1. Union,
2. Concate, dan
3. Star.
hasil-hasil operasi itu, akan tampak pada ilustrasi berikut :
Jika kita mempunyai alphabet {a,b,…,z}. Dan kita memiliki bahasa A={good,bad} dan bahasa B={boy,girl} maka :
AÈB ={good, bad, boy, girl}.
A°B ={goodboy, goodgirl, badboy, badgirl}.
A*={e,good,bad,goodgood,goodbad, badgood, badbad, goodgoodgood, goodgoodbad, …}.
mesin yang dilakukan operasi dapat dibentuk dengan mengikuti aturan operasi yang ada. silahkan baca slide, buku, dan referensi untuk pemahaman lebih lanjut.
Materi Minimum DFA dapat diambil di sini : cs3113 07 Minimum DFA
banyak pertanyaan mengenai DFA, salah satunya adalah mengenai apakah bentuk dari DFA selalu sama untuk sauatu bahasa? pertanyaan ini terjawab dengan adanya suatu bentuk minimum DFA. untuk semua bahasa yang reguler, bisa saja bentuk DFA akan berbeda. tapi jika kita sudah mengubahnya menjadi minimum DFA, maka bentuk DFA yang minimum adalah sama.
untuk mengubah DFA menjadi minimum DFA, maka ada beberapa tahap yang harus dilakukan yakni :
1. menghilangkan inaccesible state
2. mencari state yang sama / ekivalen / Indistinguishable
3. menggabungkan state yang ekivalen / Indistinguishable
4. gambar hasil penggabungan menjadi minimum DFA.
pada slide ini diperkenalkan materi NFA eMove : cs3113 06 NDFA EMove
NFA eMove adalah satu bentuk NFA yang memungkinkan pergerakan tanpa membaca apapun. pergerakan ini disebut dengan epsilon move. dengan adanya pergerakan epsilon ini, memungkinkan NFA berada di dua atau lebih state pada saat bersamaan. kondisi ini mirip dengan kondisi NFA dengan adanya transisi ambigu.
