BAB 1 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 nondeterministik 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
2
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). 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 powerful 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 tetapi berbeda 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 jadi—dalam kasus terburuk—diperlukan 2n state (Hopcroft et al., 2007).
Hopcroft et al. (2007) menyatakan bahwa salah satu bentuk perluasan dari finite automata 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
3
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. 1.2 Perumusan Masalah Berikut ini adalah perumusan masalah yang dihadapi untuk diselesaikan adalah : 1. Apakah sistem aplikasi dapat menggambarkan diagram transisi deterministik finite automata (DFA) dan non-deterministik finite automata (NFA) sesuai dengan keinginan pengguna? 2. Apakah sistem aplikasi dapat menguji dan melakukan simulasi penerimaan atau penolakan string pada automata setelah pengguna membuat diagram transisi deterministik finite automata (DFA) dan non-deterministik finite automata (NFA)? 3. Apakah sistem aplikasi dapat melakukan transformasi dari NFA ke DFA setelah pengguna membuat diagram transisi non-deterministik finite automata (NFA)?
4
1.3 Tujuan dan Manfaat 1.3.1 Tujuan Berdasarkan masalah-masalah di atas maka cakupan tujuan penelitian ini secara rinci dapat dirumuskan sebagai berikut :
1. Untuk merancang model finite state automata. 2. Untuk membuat perangkat lunak yang dapat menerima suatu input dan mengeluarkan output automata. 3. Untuk membuat perangkat lunak yang dapat melakukan pemeriksaan apakah sebuah string masukan diterima oleh suatu representasi atau tidak. 4. Untuk membuat perangkat lunak yang dapat melakukan transformasi representasi automata. 5. Supaya mahasiswa dapat lebih mengerti isi dari Teori Bahasa dan Automata, khususnya deterministik finite automata (DFA) dan non- deterministik finite automata (NFA) dan dapat mengembangkannya sehingga nilai mahasiswa menjadi lebih baik. 1.3.2 Manfaat Dengan mengacu pada tujuan penelitian di atas, maka manfaat penelitian meliputi hal-hal sebagai berikut : 1. Bagi peneliti : Dapat menghasilkan perangkat lunak yang dapat membantu pembelajaran mata kuliah teori bahasa dan otomata, dan dapat meningkatkan
5
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). 2. Bagi mahasiswa : Lebih mengerti dalam mengerjakan tugas-tugas, UTS, maupun UAS khususnya mengenai deterministik finite automata (DFA) dan non- deterministik finite automata (NFA). 3. Bagi Dosen : Dapat mengembangkan soal-soal ujian dan tugas-tugas untuk mahasiswa. 1.4 Ruang Lingkup Program aplikasi yang akan dibuat adalah sebuah program aplikasi yang dapat membantu pengguna memahami cara melakukan pengujian dalam membuat diagram transisi, matriks transisi, fungsi transisi, dan language (ekspresi regular) deterministik finite automata dan non-deterministik finite automata yang dihasilkan. Perancangan program aplikasi ini akan menggunakan bahasa pemrograman Java yang diuji cobakan pada IDE eclipse. Program ini akan dijalankan dengan menggunakan sistem operasi Microsoft Windows 7 Home Premium. 1.5 Penelitian Relevan 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
6
Automata” di Universitas Gajah Mada. Perbedaan skripsi ini dengan perancangan program yang telah dibuat tersebut antara lain : a. Cakupan kemampuan pembuktian aplikasi Dalam penelitian sebelumnya program aplikasi hanya mencakup mampu untuk melakukan 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. Pada skripsi ini, program yang dirancang mempunyai kemampuan untuk menguji DFA dan NFA dengan membuat diagram transisinya serta dapat menentukan string yang diinput dari pemgguna dapat diterima atau ditolak. b. Tampilan Program Pada skripsi ini akan dibuat desain tampilan antarmuka (interface) pengguna untuk lebih memudahkan navigasi pengguna dalam beralih antar modul dalam program. 1.6 Metodologi Penelitian Berikut adalah metode yang di gunakan dalam penulisan skripsi : a. Studi Pustaka Penulis mencari sumber buku, artikel, dan literatur internet yang berhubungan dengan topik penelitian skripsi. Penulis kemudian mempelajari dan memahami
7
materi tersebut sebagai penunjang dalam kaitannya dengan materi yang di pilih serta penelitian yang pernah dilakukan sebelumnya. b. Metode Perancangan. Dalam proses perancangan program aplikasi ini, digunakan metode Waterfall yaitu dimulai dari tahap analisis, desain, kode, pengujian, dan pemeliharaan. 1.7 Sistematika Penulisan BAB 1. PENDAHULUAN Pada bab ini akan dijelaskan mengenai latar belakang, ruang lingkup, tujuan dan manfaat, metodologi penelitian dan sistematika penulisan yang dipakai dalam penulisan skripsi ini. BAB 2. LANDASAN TEORI Pada bab ini akan dijelaskan mengenai teori dasar dan metode yang dilakukan untuk mendukung analisis dan perancangan yang dilakukan pada penulisan skripsi ini. BAB 3. ANALISIS DAN PERANCANGAN SISTEM Pada bab ini dilakukan analisis sistem yang meliputi gambaran umum permasalahan yang dihadapi, usulan pemecahan tersebut serta kebutuhan dan rancangan sistem yang diusulkan.
8
BAB 4. IMPLEMENTASI DAN EVALUASI SISTEM Pada bab ini akan dijelaskan mengenai spesifikasi perangkat keras yang dibutuhkan dalam perancangan sistem, contoh pengimplementasian sistem, evaluasi hasil sistem serta evaluasi sistem. BAB 5. KESIMPULAN DAN SARAN Pada bab ini berisi tentang kesimpulan dan keseluruhan analisis dan perancangan sistem yang telah dilakukan, selain itu bab ini juga berisi tentang saran untuk pengembangan selanjutnya.
