Ekivalensi Non-Deterministic Automata ke Deterministic Finite Automata
KATA PENGANTAR
Puji syukur kehadirat Allah SWT, yang mana berkat rahmat kesehatan, keselamatan dan juga kesempatannyalah kami bisa menyusun makalah ini dengan semaksimal mungkin dan untuk mendapatkan hasil yang sebaik – baiknya.
Terima kasih juga kepada Bapak dosen Pembimbing Teori Bahasa dan Otomata yang telah memberi kami arahan untuk menyelesaikan tugas pembuatan makalah tentang Ekuivalensi Non-Deterministic Finite Automata ke Deterministic Finite Automata
Makalah ini kami susun dengan cara mencari data dari internet dan bahan yang telah ada di buku. Semoga dengan diberikannya tugas ini kami akan mendapatkan wawasan yang lebih luas lagi, karena kami menyadari bahwa wawasan dan pengetahuan yang kami miliki sekarang masih sangat minim.
Semoga dengan selesinya tentang Ekuivalensi Non-Deterministic Finite Automata ke Deterministic Finite Automata ini dapat membantu kami untuk mendapatkan nilai yang baik dan juga dapat dibaca oleh orang lain sehingga dapat menambah wawasan bagi sipembaca itu sendiri. Dan kami juga ingin meminta maaf kepada Bapak dosen pembimbing apabila rangkuman yang kami buat masih jauh dari sempurna dan tidak sesuai dengan yang Ibu harapkan.
Pekanbaru, 18 Maret 2015
Penyusun
BAB I
PENDAHULUAN
1.1.Latar Belakang
Dalam hierarki kelas-kelas bahasa menurut Chomsky, kelas bahasa yang paling sederhana adalah kelas bahasa reguler (regular languages). Bahasa reguler dapat dengan tepat dideskripsikan dengan menggunakan finite automata (FA); dengan kata lain bahasa yang dapat diterima oleh suatu finite automata adalah bahasa reguler. Finite automata merupakan mesin abstrak yang berupa sistem model matematika dengan masukan dan keluaran diskrit yang dapat mengenali bahasa paling sederhana (bahasa reguler) dan dapat diimplementasikan secara nyata di mana sistem dapat berada di salah satu dari sejumlah berhingga konfigurasi internal disebut state. Banyak model perangkat keras dan perangkat lunak yang menggunakan finite automata sebagai penerapannya. Beberapa contoh penerapan finite automata dalam perangat keras dan perangkat lunak adalah dalam perancangan dan pemantauan perilaku rangkaian digital,scanning dokumen teks dalam halaman web guna menemukan kesamaan kata, frase dan bentuk lain (Hopcroft et al., 2007). Terdapat dua jenis finite automata, yaitu deterministik finite automata (DFA) dan non-deterministik finite automata (NFA). Perbedaan di antara kedua jenis finite automata tersebut terletak pada kontrol terhadap finite automata tersebut (Hopcroft et al., 2007). Walaupun berbeda dalam sifatnya namun kedua jenis afinite automata ini memiliki euivalensi.
1.2. Rumusan Masalah
Dari latar belakang tersebut dapat dirumuskan beberapa masalah yakni :
1.Apa itu DFA(Deterministic Finite Automata)?
2.Apa itu NFA(Non-deterministic Finite Automata)?
3.Bagaimana ekuivalensi NFA ke DFA?
1.3. Tujuan
Tujuan dari dibuatnya makalah ini adalah untuk mengetahui lebih jauh tentang DFA,NFA dan ekuivalensinya.
BAB II
PEMBAHASAN
2.1. Pengertian Deterministic Finite Automata
Deterministic Finite Automata merupakan sebuah fungsi yang harus terdefinisi untuk semuapasangan state-input yang ada didalam Q X ∑. Deterministik finite automata (DFA) bersifat deterministik, yang berarti bahwa automata tersebut tidak dapat berada di lebih dari satu state pada saat yang bersamaan.
2.2. Pengertian Non-Determinaistic Finite Automata
Non-deterministik finite automata (NFA) bersifat non-deterministik, yang berarti bahwa automata tersebut dapat berada di beberapa state pada saat yang bersamaan atau dengan kata lain NFA dapat menebak di state mana dia berikutnya akan berada (Hopcroft et al., 2007).Pada Non-Determinaistic Finite Automata (NFA) dari suatu state bisa terdapat 0,1, atau lebih busur keluar (transisi) berlabel simbol input yang sama. Non-Determinaistic Finite Automata didefenisikan pula dengan lima(5) M=(Q , Σ , δ , S , F )dengan arti yang serupa pada Deterministic Fnite Automata. Disini perbedaan ada padafungsi transisinya, dimana untuk setiap pasangan state-input, kita bisa memiliki 0 (nol) atau lebih pilihan untuk state berikutnya.
2.3.Ekivalensi-Deterministic Automata ke Deterministic Finite Automata
Ada banyak bahasa yang apabila digunakan akan membuat NFA lebih mudah dibangun dibandingkan jika dibangun menggunakan DFA. Suatu bahasa yang dibangun menggunakan NFA ternyata tidak lebih powerfull dibandingkan dengan ketika dibangun menggunakan DFA. Setiap bahasa yang dapat dideskripsikan oleh suatu NFA ternyata dapat pula dideskripsikan oleh satu DFA. Bukti bahwa DFA dapat melakukan apa saja yang dapat dilakukan NFA melibatkan suatu konstruksi yang disebut dengan subset construction. Subset construction adalah prosedur untuk mentransformasikan suatu NFA menjadi DFA (Hopcroft et al., 2007). Jumlah state yang dimiliki oleh DFA maupun oleh NFA kurang lebih sama pada kebanyakan kasus tetapiberbeda dalam jumlah transisi yang dimiliki oleh keduanya. Pada sebagian kecil kasus, untuk membuat suatu DFA yang mengungkapkan bahasa yang sama dengan suatu NFA dengan jumlah state n, bisa jadidalam kasus terburukdiperlukan 2 state (Hopcroft et al., 2007). Hopcroft et al. (2007) menyatakan bahwa salah satu bentuk perluasan dari finiteautomata adalah finite automata dengan transisi epsilon (ǫ). NFA yang memiliki ǫ (ǫ-NFA)memungkinkan NFA tersebut untuk menerima transisi ǫ atau string kosong.Lebih lanjut efeknya pada NFA adalah memungkinkan terjadinya transisi spontan tanpa menerima simbol masukan. Seperti halnya sifat non-deterministik pada finite automata, penambahan transisi ǫ ini tidak memperluas kelas bahasa yang dapat diterima oleh suatu finite automata. Perluasan ini hanya akan memberikan kemudahan dalam membangun suatu automata. DFA hasil transformasi dari suatu NFA bukanlah suatu DFA yang minimal. Untuk suatu DFA, dapat menemukan DFA yang ekuivalen yang memiliki jumlah state yang lebih sedikit atau sama dengan semua DFA yang menerima bahasa yang sama (Hopcroft et al., 2007). Selain itu juga, untuk membantu mahasiswa dan dosen dalam hal pengujian DFA dan NFA maka dibuatlah sebuah compiler yang dapat menunjukkan perubahan suatu finite automata dari suatu bentuk representasi ke bentuk representasi yang lain.
Tahapan Pengubahan Non-Determinaistic Finite Automata ke Deterministic Finite Automata Dari semua mesin Non-deterministic Finite Automata dapat dibuat mesin Deterministic Finite Automata-nya yang ekivalen (bersesuaian).Ekivalensi disini artinya mampu menerima bahasa yang sama.
Gambar 2.1 Mesin DFA
Gambar 2.2Mesin NFA
Meskipun yang satu deteministic dan lainnya non-deterministic, kedua-duanya menerima bahasa yang sama, yang dalam ekspresi regular=0 (01).
Gambar 2.3 Mesin Automata DFA
Bagaimana membuat suatu Deterministic Finite Automata yang ekuivalen dengan sebuah Non-deterministic Finite Automata?. Dimisalkan ingin membuat mesin Deterministic Finite Automata dari mesin Non-deterministic Finite Automatalangkah awalnya yang harus dilakukan adalah membuat tabel transisi NFA tersebut. Bila diketahui ∑={0,1}, maka tabel transisinya adalah sebagai berikut.
Δ
0
1
q0
{q0, q1}
{q1}
q1
∅
{q0, q1}
Dengan adanya tabel transisi tersebut akan mempermudah kita melakukan langkah selanjutnya. Untuk memulai dari state awal, kemudian mengikuti transisinya untuk membentuk state-state baru, untuk setiap state yang terbentuk diikuti lagi transisinya sampai ter’cover’ semua. Dimulai dengan state awal q0, seperti contoh dibawah ini.
Gambar 2.4 Mulai dengan state awal
Selanjtnya, telusuri berikutnya yang diperoleh dengan memanfaatkan tabel transisinya:
•
State {q0}bila memperoleh input 0 menjadi state{q0, q1}.
•
State {q0} bila memperoleh input 1 menjadi state {q1}.
Hasilnya dapat dilihat dibawah ini.
Gambar 2.5 Hasil dari pemnelusuran {q0}
Selanjutnya, kita telusuri state-statebaru yang terbentuk :
•
State q1 memperoleh input 0 menjadi state ∅
•
State {q1}bila memperoleh input 1 menjadi state {q0, q1}.
•
State {q0, q1}bila memperoleh input 0 menjadi state {q0, q1}, ini diperoleh dari δ{q0, q1}={q0, q1}digabung dengan δ{q0, q1},=∅, maka hasilnya d({q0, q1},0) = {q0, q1};
•
State{ q0, q1} bila memperoleh input 1 menjadi state {q0, q1}, ini diperoleh dari δ{q0, 1}={q1} digabung dengan δ{q=0, 1}= {q0, q1}, maka hasilnya δ({q0, q1}, 1)= {q0, q1}.
Gambar 2.6 Hasil setelah penelusuran {q1} dan {q0, q1}
Selanjutnya, dapat dilihat semua state yang sudah ditelusuri/dirunut, tinggal state ∅. state ∅ menerima input 0 atau 1 menjadi state ∅, atau δ(∅,0)= ∅ dan δ(∅,1)= ∅. Hasilnya dapat dilihat dibawah ini.
Gambar 2.7 Hasil setelah semua ditelusuri.
Dapat diingat padamesin Non-deterministic Finite Automata semula himpunan state akhir adalah {q1}, maka pada Deterministic Finite Automata hasil perubahan state-state akhir adalahsemua state yang mengandung{q1}. Maka, state akhirnya sekarang adalah state {q1} dan {q0, q1}, atau secara formal.
F={{ q1},{q0, q1}}
Dengan demikian, Deterministic Finite Automatahasil ekuivalensidengan Non-Deterministic Finite Automata dapat dilihat pada gambar dibawah ini.
Gambar 2.8 Mesin DFA yang ekuivalen dengan NFA
Kita dapat memriksa apakah kedua otomata tersebut ekuivalen. Untuk membuktikannya kita perlu memperlihatkan bahwa suatu bahasa yang diterima oleh Non-DeterministicFinite Automata ekivalenya tersebut. Bila diketahui Non-Deterministic Finite Automata semula menerima string ‘001’, maka seharusnya Deterministic Finite Automata juga menerimastring tersebut. Dapat dilihat :
δ (q0,001) = δ ({q0, q1},01) = δ ({q0, q1},1) = {q0, q1}
Karena state {q0, q1} termasuk state akhir, maka berarti string tersebut diterima.
Contoh-contoh Ekivalensi Non-deterministic Finite Automata ke Deterministic Finite Automata
Contoh-contoh lain ekivalensi Non-Deterministic Finite Automata ke Deterministic Finite Automata.
Gambar 2.9 Mesin NFA
Tabel transisi untuk NFA, bila diketahui Σ = {a,b}:
δ
A
b
q0
{q0, q1}
{ q1}
q1
∅
∅
Mesin Deterministic Finite Automata ekivalensi dari Non-Determnistic Finite Automata tersebut dapat dilihat pada gambar dibawah ini.
Gambar 3.0 DFA yang ekivalensi dengan NFA pada gambar 2.9
Gambar 3.1 Mesin NFA
Tabel transisi untuk Non-Deterministic Finite Automata pada gambar dibawah ini, bila diketahui Σ = {a,b}:
δ
a
b
q0
∅
∅
Mesin Detrministic Finite Automataekivalensi dari Non-Deterministic Finite Automata tersebut bisa dilihat pada gambar dibawah ini.
Gambar 3.2 DFA yang ekivalen dengan NFA pada gambar 3.1
Gambar 3.3Mesin NFA
Tabel transisi untuk Non-Deterministic Finite Automata ekivalensi dari Non-Deterministic Finite Automata tersebut dapat dilihat seperti diabwah ini.
Gambar 3.4DFA yang ekivalen dengan NFA pada gambar 3.3
BAB III
PENUTUP
3.1. Kesimpulan
Dari pembahasan daiatas dapat disimpulkan bahwa antara NFA ke DFA terdapat ekuivalensi.Dengan menggunakan tabel transisi kita dapat lebih mudah menentukan ekuivalensi dari NFA ke DFA atau sebaliknya.
DAFTAR PUSTAKA
BINUS.Tesis. 18 Maret 2015.
Utdirartatmo, Finrar. (2007). Teori Bahasa dan Otomata.Graha Ilmu
