PEMODELAN PERANGKAT LUNAK UNTUK PENGERTIAN DETERMINISTIC FINITE AUTOMATA DAN NON-DETERMINISTIC FINITE AUTOMATA Santa Meilisa; Ngarap Im Manik; Djunaidy Santoso Universitas Bina Nusantara, Jl. Mawar Bukit Nusa Indah No. 106, Ciputat 15414, 021-7406519,
[email protected]
ABSTRACT In the hierarchy of Chomsky language classes, language classes are the simplest class of regular languages . Regular languages can be precisely described using finite automata (FA). There are two types of finite automata, the deterministic finite automata (DFA) and the non-deterministic finite automata (NFA).In this study will be described about application program testing of deterministic finite automata transition diagram (DFA) and non-deterministic finite automata (NFA). This application is able to describe the transition diagram of DFA and NFA and can determine the string that input from the user is accepted or rejected with the main purpose is simplify the learning of language automata theory. Development of the system is started from the making of automata structure to the implementation of the algorithm in the manufacture and handling of automata transformations. The testing is done by looking at the system in dealing with the formation and transformation of finite automata. Obtained from testing the system is able to perform formation between automata and finite automata transformation. The results of performance testing found that the system is able to handle the formation and transformation of finite automata. The design of the application program will be conducted using the Java programming language is tested on eclipse IDE.
Keywords : Finite State Automata, DFA, NFA, Java, eclipse. ABSTRAK Dalam hierarki kelas-kelas bahasa Chomsky, kelas bahasa yang paling sederhana adalah kelas bahasa reguler. Bahasa reguler dapat dengan tepat dideskripsikan dengan menggunakan finite automata (FA). Terdapat dua jenis finite automata, yaitu deterministik finite automata (DFA) dan non-deterministik finite automata (NFA). Dalam penelitian ini akan dideskripsikan program aplikasi pengujian diagram transisi deterministik finite automata (DFA) dan non-deterministik finite automata (NFA). Aplikasi ini mampu menggambarkan transisi diagram DFA dan NFA serta dapat menentukan string yang diinput dari pengguna dapat diterima atau ditolak, dengan tujuan utama memudahkan dalam membantu pembelajaran teori bahasa automata. Pengembangan sistem dilakukan mulai dari pembuatan struktur automata hingga implementasi algoritma dalam pembuatan dan penanganan transformasi automata. Pengujian dilakukan dengan melihat sistem dalam menangani pembentukan dan transformasi finite automata. Dari pengujian didapatkan bahwa sistem mampu melakukan pembentukan automata dan melakukan transformasi diantara finite automata. Hasil dari pengujian performa didapatkan bahwa sistem mampu menangani pembentukan dan transformasi finite automata. Perancangan program aplikasi akan dilakukan dengan menggunakan bahasa pemrograman Java yang diuji cobakan pada IDE eclipse. Kata kunci : Finite State Automata, DFA, NFA, Java, eclipse.
PENDAHULUAN 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 masukkan dan keluaran diskrit yang dapat mengenali bahasa paling sederhana (bahasa reguler) dan dapat diimplementasikan secara nyata dimana 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, pemindaian 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). Deterministik finite automata (DFA) bersifat deterministik, yang berarti bahwa automata tersebut tidak dapat berada di lebih dari satu state pada saat yang bersamaan, sedangkan 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). 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. Dalam menentukan topik, skripsi ini diambil referensi dari perancangan program sebelumnya yang telah dilakukan oleh Ignatius Giri Wardhana dengan judul “Finite State Automata Simulator (FAST) : Tool Untuk Simulasi dan Transformasi Finite State Automata” di Universitas Gajah Mada yang memiliki rumusan masalah yaitu mengembangkan suatu aplikasi yang dapat digunakan untuk merancang automata yang dapat menerima dan mengeluarkan output berupa file, menguji dan melakukan simulasi penerimaan atau penolakan string pada automata, melakukan transformasi di antara representasi finite automata, dan meminimalisasi automata secara menyatu dalam suatu aplikasi. Dalam penelitian ini, metode yang digunakan sama seperti penulis buat dan hasil penelitian yang dilakukan didapat bahwa sistem FAST dapat menerima masukan berupa file DFA, NFA dan -NFA, sistem ini juga telah berhasil melakukan proses pencocokan string pada ketiga finite automata tersebut serta melakukan transformasi dari NFA menjadi DFA yang ekuivalen dengan NFA awal dan melakukan minimisasi DFA pada DFA yang diketahui belum minimum menjadi DFA dengan state minimum yang ekuivalen dengan DFA awal dan sistem dapat menangani pembentukan file DFA, NFA random dan menangani subset construction dan minimisasi DFA hingga sejumlah seribu state. Penelitian berikutnya yang bertopik sama yaitu penelitian yang dilakukan oleh Milan Kynzl yang berjudul “Simulation of Nondeterministic Finite Automata using Fail Function” di Czech Technical University, Prague. Penelitian ini memiliki masalah yaitu saat meneliti masalah mengenai pattern matching dapat dipecahkan dengan menggunakan teori finite automata. Akan tetapi, jika kita membuat NFA untuk memecahkan masalah, kita tidak bisa menggunakannya secara langsung karena NFA bersifat nondeterminism, yaitu ketika membaca input string, di beberapa state NFA ada lebih dari satu kemungkinan pada langkah selanjutnya. Dalam kasus tersebut, NFA memprediksi langkah yang benar dan menggunakannya. Tapi dalam prakteknya tidak mungkin untuk memilih cara yang benar hanya untuk mengetahui state yang sebenarnya dan simbol input. Metode yang dingunakan untuk memecahkan masalah yaitu dengan membandingkan dua metode yaitu metode depth first search dan metode basic simulation. Hasil yang tercapai yaitu metode depth first search lebih unggul dalam hal kompleksitas waktu dibandingkan dengan metode basic simulation, metode depth first search tidak sensitif pada panjang pola untuk teks input yang dipilih sedangkan metode basic simulation menciptakan visible “steps” sebagai jumlah vektor bit yang diperlukan untuk mewakili state yang aktif. Perbedaan dari kedua penelitian di atas yaitu bahwa dalam penelitian sebelumnya program aplikasi hanya mencakup mampu dalam melakukan pembentukan finite automata secara terbatas, seperti pada penelitian yang dilakukan oleh Ignatius Giri Wardhana yang hanya mencakup pembentukan finite automata random sesuai dengan keinginan pengguna dan melakukan transformasi NFA menjadi DFA dan minimisasi DFA
yang dilakukan pada inputan pengguna berdasarkan file yang sudah ditentukan yang kemudian mengeluarkan hasil/output yang juga berdasarkan file yang sudah ditentukan, tapi pada skripsi ini program dibuat dengan user interface sehingga pengguna mampu berinteraksi dengan sistem lebih mudah. Sedangkan untuk penelitian yang dilakukan oleh Milan Kynzl menjelaskan bagaimana NFA dapat menentukan pola yang cocok yang diujikan dengan membandingkan dua metode yang berbeda. Adapun rumusan masalah yang harus dihadapi untuk diselesaikan yaitu apakah sistem mampu melakukan simulasi pada setiap pengujiannya dan diharapkan dapat sesuai dengan tujuan dan manfaat yang telah dibuat. Tujuan dari penelitian ini yaitu merancang model finite state automata, membuat perangkat lunak yang dapat menerima suatu input dan mengeluarkan output automata, membuat perangkat lunak yang dapat melakukan pemeriksaan apakah sebuah string masukan diterima oleh suatu representasi atau tidak, membuat perangkat lunak yang dapat melakukan transformasi representasi automata, dan supaya mahasiswa dapat lebih mengerti isi dari Teori Bahasa dan Automata, khususnya deterministik finite automata (DFA) dan nondeterministik finite automata (NFA) dan dapat mengembangkannya sehingga nilai mahasiswa menjadi lebih baik. Sedangkan manfaat dari penelitian ini dibagi menjadi tiga bagian yaitu : bagi peneliti : Dapat menghasilkan perangkat lunak yang dapat membantu pembelajaran mata kuliah teori bahasa dan otomata, dan dapat meningkatkan perkembangan studi finite state automata di Indonesia, dapat mengembangkan diri dalam hal isi dari Teori Bahasa dan Automata, khususnya deterministik finite automata (DFA) dan non-deterministik finite automata (NFA), bagi mahasiswa : Lebih mengerti dalam mengerjakan tugas-tugas, UTS, maupun UAS khususnya mengenai deterministik finite automata (DFA) dan non- deterministik finite automata (NFA), dan bagi dosen : Dapat mengembangkan soal-soal ujian dan tugas-tugas untuk mahasiswa.
Finite Automata Definisi 1 Sebuah finite automata terdiri dari lima komponen (Q, Σ, δ, q0, F ), dimana : 1. 2. 3. 4. 5.
Q adalah himpunan set berhingga yang disebut dengan himpunan states. Σ adalah himpunan berhingga alfabet dari simbol masukan. δ : Q × Σ adalah fungsi transisi, merupakan fungsi yang mengambil states dan alfabet input sebagai argumen dan menghasilkan sebuah state. Fungsi transisi sering dilambangkan dengan δ. q0 ϵ Q adalah states awal. F Q adalah himpunan states akhir.
Definisi 2 Hopcroft et al. (2007) Suatu finite automata M = (Q,Σ,δ,q0,F) akan menerima sebuah string w jika kumpulan states r0r1 · · · rn dalam Q memenuhi tiga kondisi : 1. 2. 3.
r0 = q0. δ(ri, wi+1) = ri+1 untuk i = 0, · · · , n – 1. rn ϵ F.
dengan w = w1w2...wn adalah string di mana masing-masing wi adalah anggota alphabet Σ. Pada definisi 2 kondisi yang pertama dinyatakan bahwa suatu finite automata dimulai dari start state. Pada kondisi yang kedua dinyatakan bahwa finite automata akan berpindah dari satu state ke state yang lain berdasarkan fungsi transisi, dan kondisi yang ketiga menyatakan bahwa finite automata akan menerima string masukan apabila masukan tersebut berakhir pada final state. Dapat dinyatakan bahwa M mengenali bahasa A jika A = {w | M menerima w}. Menyatakan suatu finite automata dengan menggunakan notasi 5-tuple akan sangat merepotkan. Cara yang lebih dianjurkan dalam menuliskan finite automata, yaitu dengan menggunakan : 1. 2.
Diagram transisi (transition diagram), yaitu berupa suatu graf. Tabel transisi (transition table), yaitu daftar berbentuk tabel untuk fungsi δ, yang merupakan hubungan antara himpunan states dengan alfabet input.
Penyajian FA Menggunakan Diagram Transisi Definisi 3 Diagram transisi untuk finite automata M = (Q, Σ, δ, q0, F ) adalah suatu graf yang didefinisikan sebagai berikut :
1. 2. 3. 4.
Terdapat simpul untuk setiap state Q. Untuk setiap state q ϵ Q dan setiap simbol input a ∈ Σ, berlaku δ(q, a) = p. Diagram transisi memiliki busur berlabel a dari state q ke state p. Terdapat anak panah berlabel start yang mengarah ke state awal q0 dan anak panah ini tidak berasal dari state manapun. State yang merupakan state akhir (F) akan ditandai dengan lingkaran ganda, sedang state yang lain menggunakan lingkaran tunggal.
Contoh 1 Gambar 1 memperlihatkan diagram transisi dari sebuah finite automata.
Gambar 1 Diagram Transisi dari Suatu Finite Sutomata Penyajian FA Menggunakan Tabel Transisi Tabel transisi merupakan representasi tabular dari fungsi δ yang mengambil dua argumen dan menghasilkan suatu nilai. Baris pada tabel berkorespondensi dengan state dan kolom pada tabel berkorespondensi dengan input. Contoh 2 Pada tabel 1 memperlihatkan tabel transisi dari finite automata yang diperlihatkan pada Gambar 1
Tabel 1 Tabel Transisi FA pada Contoh 1
δ q1
0
1
q1
q2
q2
q3
q2
q3
q1
q2
Tabel transisi pada contoh 2 memiliki arti : 1. Simbol pada kolom sebelah kiri adalah state. 2. Simbol pada baris paling atas adalah simbol masukan. 3. Simbol yang berada "‘dalam"’ tabel merupakan fungsi transisi. 4. Simbol panah (→) pada kolom sebelah kiri menunjukkan start simbol. 5. Simbol (*) pada kolom sebelah kiri menunjukkan state final.
Deterministik Finite Automata (DFA) Contoh 3 Diketahui suatu DFA M = (Q, Σ, δ, q0, F ) dimana Q = {q0, q1, q2} , Σ = {0,1}, F = {q1} dan δ adalah fungsi yang didefinisikan sesuai dengan Tabel transisi 2 :
Tabel 2 Tabel Transisi DFA yang Menerima Akhiran 01
δ q0
0
1
q2
q0
q1
q1
q1
q2
q2
q1
Dari Tabel transisi 2 dapat dibuat suatu diagram transisi sesuai dengan Gambar 2 :
Gambar 2 Diagram Transisi DFA yang Menerima Akhiran 01 Contoh 4 Diberikan suatu DFA M seperti pada contoh M menerima string 000 dan 010. Solusi: jalur komputasi dari string 000 adalah :
sehingga δ(q0, 000) ϵ F dan M menerima string 000. Dengan cara yang sama dapat diketahui bahwa δ(q0, 010) = q3 ϵ F dan M menolak 010.
Non-deterministik Finite Automata (NFA) Definisi 4 Suatu non-deterministik finite automata (NFA) tersusun atas quintuple M = (K, Σ, δ, s, F ) dimana : 1. K adalah himpunan state, 2. Σ adalah alfabet, 3. s ϵ K adalah state awal, dan 4. δ adalah relasi transisi, di mana K × (Σ ϵ {e}) × K Contoh 5 Diberikan suatu NFA M = ({q0, q1, q2, q3} , {0, 1} , δ, q0, {q3}) dengan tabel transisi
δ q0
0
1
q1
⊘
q1
q1
{q1, q2}
q2
⊘
q3
q3
q3
q3
Jika x = 0111, maka dapat dilihat apakah x diterima oleh NFA M atau tidak dengan melakukan proses: δ1({q0} , 0) = δ(q0, 0) = {q1} δ1({q0} , 01) = δ1(δ1({q0} , 0), 1) = δ1({q1} , 1) = δ(q1, 1) = {q1, q2} δ1({q0} , 011) = δ1(δ1({q0} , 01), 1) = δ1({q1, q2} , 1) = δ(q1, 1) ∪ δ(q2, 1) = {q1, q2} ∪ {q3} = {q1, q2, q3}
δ1({q0} , 0111) = δ1(δ1({q0} , 011), 1) = δ1({q1, q2, q3} , 1) = δ(q1, 1) ∪ δ(q2, 1) ∪ δ(q3,1) = {q1,q2} ∪ {q3} ∪ {q3} = {q1,q2,q3} δ1({q0} , 0111) = {q1, q2, q3} dan memuat q3 yang merupakan anggota himpunan dari final state. Oleh karena terdapat satu buah jalur komputasi dari initial state yang berakhir pada salah satu anggota himpunan final state F , maka dapat dikatakan bahwa x = 0111 diterima oleh NFA. Dengan demikian, dapat dikatakan bahwa jika M adalah suatu NFA maka bahasa yang diterima oleh NFA dapat didefinisikan sebagai L(M ) = {x|δ1({q0} x) = P} dimana P memuat minimal satu buah anggota F (Kakde, 2002).
Transformasi NFA - DFA (Subset Construction) Walaupun lebih mudah untuk dibangun, suatu NFA hanyalah mesin ideal yang tidak dapat dengan efisien diimplementasikan dalam kehidupan nyata karena mesin yang sesungguhnya hanya dapat mengikuti satu jalur komputasi pada saat yang bersamaan (Du dan Ko, 2001). Untuk itu diperlukan suatu prosedur yang dapat melakukan transformasi dari suatu NFA menjadi DFA yang ekuivalen dengan bahasa yang diterima NFA tersebut. Transformasi suatu NFA menjadi DFA dilakukan dengan melakukan simulasi semua jalur transisi yang mungkin pada NFA. Suatu NFA memiliki n buah state maka DFA yang ekuivalen dengan NFA tersebut akan memiliki 2n state dengan state awal pada DFA tersebut merupakan subset {q0} dengan demikian, transformasi dari NFA menjadi DFA meliputi pencarian semua subset yang mungkin dari himpunan state dari NFA. (Kakde, 2002). Ide dasar dari subset construction adalah bahwa masing-masing state pada DFA yang terbentuk berkorespondensi dengan himpunan state pada NFA. Terdapat kemungkinan bahwa jumlah state pada DFA yang terbentuk dari hasil subset construction adalah berjumlah eksponensial dari jumlah state dari NFA. Contoh 6 Diketahui suatu NFA M = (Q,{0,1},δ,q0,F) dan diberikan Q = {q0, q1, q2, q3, q4, q5}, F = {q3, q4} dan tabel transisi
δ q0
0
1
ǫ
{q0}
{q0, q2}
{q1}
q1
{q5}
{q2}
−
q2 q3 q4
{q3}
− −
− {q4} −
q5
−
− {q4}
− {q3}
−
Lihat Gambar 3 untuk mengetahui digram transisi NFA. akan dibentuk DFA M ′ yang ekuivalen dengan NFA M.
Gambar 3 NFA Masukan Subset Construction
solusi: dapat dibentuk DFA M ′ dengan cara : 1. 2.
Buat Qϵ = ϵ − closure({q0}) sebagai initial state dan F ′ = ⊘ menjadi himpunan final state. Buat Q′ = {Qϵ}. Jika Qϵ ∩ F = ⊘ kemudian tambahkan Qϵ dalam F ′. Ulangi langkah tersebut sampai ϵ′(Qx, a) didefinisikan untuk semua Qx ϵ Q′ dan semua a ϵ {0, 1} :
a) Pilih Qx ϵ Q′ dan a ϵ {0, 1} sedemikian hingga δ′(Qx, a) belum didefinisikan. b) Buat Qxa = δ(Qx, a) c) Jika Qxa ϵ Q′ tambahkan Qxa ke Q′ dan tambahkan juga pada F ′ jika Qxa ∩ F = ⊘ Semua proses tersebut dapat dilihat pada tabel transisi
δ′
0
1
Q = {q0, q1}
{q0, q1, q5}
{q0, q1,q2}
Q0 = {q0, q1, q5}
{q0, q1, q5} = Q0
{q0, q1,q2, q4}
Q1 = {q0, q1, q2}
{q0, q1, q3, q4, q5}
{q0, q1,q2} = Q1
Q01 = {q0, q1, q2, q4}
{q0, q1, q3, q4, q5}
{q0, q1,q2} = Q1
Q10 = {q0, q1, q3, q4, q5}
{q0, q1, q3, q4, q5} = Q10
{q0, q1, q2, q4} = Q01
Perlu dicatat bahwa pada langkah 2 tidak perlu mempertimbangkan states Q00, Q000, Q001 dan yang lainnya karena Q00 = Q0, Q000 = Q00 = Q0 dan Q001 = Q01, dengan cara yang hampir sama dapat diperoleh Q11 = Q1 tidak perlu memperhitungkan Q11W untuk sebarang W ϵ {0, 1}*. Transisi diagram dari DFA M ′ ditunjukkan pada Gambar 4.
Gambar 4 DFA Hasil Subset Construction yang Ekuivalen
METODE PENELITIAN Dalam penelitian ini metode yang digunakan meliputi :
Studi Pustaka Penulis mencari sumber buku, artikel, dan literatur internet yang berhubungan dengan topik penelitian skripsi. Penulis kemudian mempelajari dan memahami materi tersebut sebagai penunjang dalam kaitannya dengan materi yang di pilih serta penelitian yang pernah dilakukan sebelumnya.
Metode Perancangan Dalam proses perancangan program aplikasi ini, digunakan metode Waterfall yaitu dimulai dari tahap analisis, desain, kode, pengujian, dan pemeliharaan.
HASIL DAN BAHASAN Program utama dari aplikasi pengujian ini terdiri dari 1 buah form dengan 5 modul, yaitu modul Menggambarkan Diagram Transisi DFA, modul Pengujian Inputan String DFA, modul Menggambarkan Diagram Transisi NFA, modul Pengujian Inputan String NFA, dan modul Transformasi NFA ke DFA.
TAMPILAN HASIL
Gambar 1 Rancangan Tampilan Untuk menggambarkan Diagram Transisi DFA Modul ini akan muncul ketika program pertama kali dijalankan. Pada modul ini pengguna harus memilih automaton apakah pengguna ingin menggambarkan diagram transisi DFA atau NFA. Setelah memilih automaton, yang dalam hal ini pengguna memilih automaton DFA dan pengguna langsung dapat menggambar diagram transisinya. Untuk Toolbar merupakan toolbar yang pertama kali digunakan oleh pengguna berfungsi untuk men-select selama pengguna menggambar diagram transisi DFA atau memilih menu instruksi yang dibutuhkan pengguna dalam menggambar diagram transisi atau melakukan pengujian string ataupun melakukan transformasi dari NFA ke DFA, sedangkan untuk toolbar digunakan untuk membuat state, toolbar ini pada saat pertama kali dibuat, sistem akan menanyakan apakah nama dari state yang ingin dibuat tersebut dan sekaligus dapat menentukan mana yang start state atau final state dengan mngklik kanan pada mouse serta dapat menghapus state tersebut apabila sudah tidak digunakan lagi, dan untuk toolbar digunakan untuk memberikan link antar state dan memberi nilai pada link tersebut. Link tersebut nantinya akan berguna sebagai pengujian string apakah string tersebut diterima atau tidak. String yang dimasukkan harus sesuai dengan nilai yang dibuat pada penggmabaran diagram transisi DFA atau NFA. Cara mengubahnya hanya dengan mengganti textedit pada Alphabet dengan nilai yang pengguna buat.
Gambar 2 Rancangan Tampilan Untuk Pengujian Inputan String Pada DFA Pada gambar 2 di atas, setelah pengguna menggambar diagram transisi DFA, pengguna dapat melakukan pengujian inputan string dengan memasukkan inputan ke textbox string. Kemudian tekan tombol Run. Saat tombol Run ditekan, sistem akan memeriksa apakah string yang dimasukkan tersebut menuju ke final state. Jika menuju ke final state, maka string tersebut ACCEPTED, jika tidak menuju ke final state maka REJECTED. Di sini juga pengguna dapat melihat hasil running secara langkah per langkah, yaitu dengan memilih menu Run -> Debug -> Debug One Step. Atau pengguna juga dapat melihat hasil running sekaligus melihat hasilnya, yaitu dengan memilih menu Run -> Debug -> Debug Proceed. Langkah-langkah yang dimaksud pada saat pengguna menjalankan instruksi Debug One Step atau Debug Proceed, sistem akan memberi garis merah pada link atau penghubung antar state bila string tidak menuju ke final state, sedangkan sistem akan memberi garis hijau bila string menuju ke final state. Saat sistem selesai melakukan instruksi tersebut, sistem akan mengeluarkan peringatan apakah string yang telah dimasukkan oleh pengguna tersebut dapat diterima atau ditolak.
Gambar 3 Rancangan Tampilan Untuk menggambarkan Diagram Transisi NFA Pada gambar 3 di atas menunjukkan apabila pengguna memilih automaton NFA dan kemudian pengguna menggambarkan diagram transisi NFA sesuai dengan keinginan pengguna serta memiliki fungsi yang sama seperti yang telah dijelaskan pada gambar 1 di atas
Gambar 4 Rancangan Tampilan Untuk Pengujian Inputan String Pada NFA Pada gambar 4 di atas, setelah pengguna menggambar diagram transisi NFA, kemudian pengguna dapat melakukan pengujian inputan string pada diagram transisi NFA yang dimasukkan sesuai dengan keinginan pengguna serta memiliki fungsi yang sama seperti yang telah dijelaskan pada gambar 2.
Gambar 5 Rancangan Tampilan Hasil Transformasi NFA ke DFA
PEMBAHASAN Untuk mengevaluasi kinerja sistem apakah dapat melakukan pengujian dengan tepat atau tidak, akan dilakukan pencobaan dengan sampel automata yang sudah ada. Untuk tujuan pencobaan ini finite automata dibagi menjadi dua jenis, yaitu : o o
Deterministik finite automata (DFA). Bersifat deterministik, yaitu setiap input alphabet/simbol dari suatu state hanya akan bertransisi ke satu state lain. Non-deterministik finite automata (NFA). Bersifat non-deterministik, yaitu setiap input alphabet/simbol dari suatu state mungkin akan bertransisi ke lebih dari satu state lain.
Tampilan keluaran dari hasil pengujian Deterministik finite automata yaitu didapat bahwa input string kata ababbabb adalah ACCEPTED yang dikarenakan string yang diinput menuju ke final state. Sedangkan tampilan keluaran dari hasil pengujian non-deterministik finite automata yaitu didapat bahwa kata 100111 REJECTED, yang dikarenakan string yang diinput tidak menuju ke final state. Selain itu juga tampilan keluaran untuk hasil transformasi NFA ke DFA yaitu :
Tabel 1 Matriks Transisi DFA Hasil Transformasi NFA State
0
1
A
{AB}
{A}
AB
{ABC}
{A}
BC
{ABC}
{A}
Berdasarkan pada tabel 1, maka dapat dibuat diagram transisi DFA seperti gambar berikut :
Gambar 6 Diagram Transisi DFA Hasil Transformasi NFA
SIMPULAN DAN SARAN Dari analisis dan pengujian terhadap beberapa sampel teori bahasa dan automata, dapat disimpulkan bahwa program pengujian dapat memberikan hasil yang sesuai dengan bila dikerjakan secara manual. Waktu kerja yang dibutuhkan program dalam memberikan hasil pengujian sangat singkat, sehingga jauh lebih efisien bila dibandingkan dengan pengujian secara manual. Program telah diuji dengan beberapa sampel automata yang memiliki jumlah state yang bervariasi, dan tidak ditemukan peningkatan waktu yang kasat dalam waktu proses program. Ukuran file program kecil dan algoritma program dirancang dengan algoritma-algoritma dasar yang tidak kompleks, sehingga tidak membutuhkan spesifikasi komputer yang tinggi untuk menjalankan program. Program dinilai dapat memenuhi tujuannya untuk memudahkan pengguna dalam memahami teori bahasa dan automata, khususnya mengenai deterministik finite automata (DFA) dan non-deterministik finite automata (NFA).
REFERENSI Ding-Zhu, Du., dan Ko, K-I. (2001). Problem Solving in Automata, Languages, and Complexity. John Wiley and Son, Inc. ISBN 0-471-22464-2. Hopcroft, J E., Motwani, R., dan Ullman, J D. (2007). Introduction to Automata Theory, Languages and Computation. Pearson Addison-Wesley, Upper Saddle River, NJ, 3. edition, 2007. ISBN 978-0-321-51448-6. Kakde, O.G. (2002). Algorithms for Compiler Design. Charles River Media, Inc. ISBN 1-58450-100-6. Milan Kynzl. (2006). Simulation of Nondeterministic Finite Automata using Fail Function. Disertasi tidak diterbitkan. Prague: Faculty of Electrical Engineering, Czech Technical University.
RIWAYAT PENULIS Santa Meilisa lahir di kota Padang pada 29 Mei 1989. Penulis menamatkan pendidikan S1 di Universitas Bina Nusantara dalam bidang Teknik Informatika dan Matematika pada 2012. Penulis aktif di humas sebagai tim kreatif.
