|
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 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
|
|
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 2
n
state (Hopcroft et al., 2007).
Hopcroft et al. (2007) menyatakan bahwa salah satu bentuk perluasan dari finite
automata adalah finite automata dengan transisi epsilon (o). NFA yang memiliki
o
(o-
NFA) memungkinkan NFA tersebut untuk menerima transisi o 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
o
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
?nite au
tomata 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.
|