SIMUTATOR FINITE AIITOMATA SEBAGAI AI,AT PERANCANG REGULAR TANGUAGE lr.
M.Kom * Mauknr,Skom,MMT* Nathanael Pramudita""
Y ohanes Bow o W idodo,
Abstract lncredible growth of computer performance has gioen many chances to aarious computing area. Computer ptrogramffiing languages and compilers haae grown zsery fast proaiding us oarious problem sokting choices. There are many methodologies in computer programming language. Functionalprogramming,proceduralprogramming, object orientedprogramming and so on, are concepts aaailable in computer languages now days. The growth of such techniques could not be separated from their basic theoretical foundations. This research discussu one aspect of thebasictheoreticalfoundationin cornputerlangunge. Finite Automaton is ztery basic foundation. It is a mathematical model of language recognizer and language generator. This research deals with how to simulate the behaoiors of Finite Automaton and erploreit to modelrecognition and generationof simplelnnguages.Innguagesbeinghandled are tly ones with aery limited alphabet, but could represent handling of more complicated languages in the same class. Theoretically,languages generated and recognized by Finite Automaton are languages in the class of Regular Languages. These languages could be represented by seaeral mean, regular expressions and regular grammars are some of the choices. Besides, its also could be described using mere natural human language. The experiments haae been done girsing conclusion thnt the simulator could simulate the behartior of Finite Automata in aery sirnple and easy rnanner. It giaing us confidence thnt the simulator
couldbe used as a tool inlearning of languages theory. lt also couldbe used to support design of simple languages, and in some way could be deaeloped to support the design of more complicated comput er languages.
1.
LATAR BELAKANG
Pada saat sekarang ini banyak dikembangkan kompilator untuk bahasabahasa komputer misalnya Basic, Pascal, C, Fortran,lava, dan lain-lain. Setiap
bahasa memiliki ciri khas, keunggulan-kelemahan, dan tata penulisan tersendiri. Untuk dapat merancang struktur sintaks yang baik, perlu landasan teoritis cukup kuat. Landasan teoritis tersebut meliputi teori mengenaibahasa (language) dan mesin pengenal bahasa tersebut.
* Dosen Jurusan Teknik Informatika Universitas Pelita Harapan ** Mahasiswa Jurusan Teknik Informatika Universitas Pelita Harapan
Vol. 5, No.2, Agustus 2002
89
Finite Automata adalah tool untuk language generator danlanguage recognizer. Pembuatan simulator automata dapat mempermudah rancangan suatu bahasa yang termasuk dalam Regular Language, sekaligus memberikan pemahaman yang lebih jelas mengenai cara kerja Finite Automata sebagai pengenal bahasa tersebut. Penelitian ini memiliki peran yang penting dalam studi pengembangan teori bahasa yang pada akhirnya dapat digunakan untuk dasar pembuatan berbagai kompilator, baik dalam tahap analisis leksikal, sintaks, mauPun semantik.
2.
STRING, ALPHABET DAN BAHASA (LANGUAGE)
Simbol adalah sebuah entiti abstrak yang tidak didefinisikan secara formal, misalnya huruf dan angka. String adalah serangkaian urutan simbol yang berurutan, misalnya a,b, c adalah simbol dan abc kita sebut sebagai string. Panjang sebuah string w dilambangkan dengan I w I dimana nilainya adalah jumlah dari simbol yang membentuk string w tersebut, misalnya #rtng abcd mempunyai panjang sebesar 4. String yang tidak mempunyai simbol disebut sebagai string kosong yang dilambangkan dengan e. Concatenation dari dua string adalah string yang terbentuk dari string pertama ditambah dengan string kedua tanpa ada spasi pemisah, misalkan w = makan dan x = nasi maka concatenation dati wx = makannasiAlphabet adalah himpunan dari simbol-simbol. Bahasa (Language) adalah himpunan string yang terbentuk dari simbol-simbol yang berada dalam himpunan alphabet. Bahasa dilambangkan dengan I* dan alphabet dilambangkan dengan X, misalkan I={a} maka )* = {t, a, aa, aaa, aaaa, ...1. Operasi-operasi yang terdapat dalam bahasa antara lain :
a.
Union Llnionantarabahasa L danM ditulis denganL
uM,
dimana L
uM
= {a
I
ae Latau acMl.
b.
Concatenation Concatenation antarabahasa L d.an M ditulis dengan LM, dimana LM = {a
b laqLdan bEM).
90
Vol. 5, No.2, Agustus 2002
c.
Kleene Closure Kleene Closuredari bahasa
L ditulis d.engan L*, diman a L*
=y f i=0
d.
Positive Closure Positiae Closure dari bahasa L ditulis dalam L*,
3.
t =ir: dimana =^,
REGULAR EXPRESSION
Regular Expression adalah suafu ekspresi sederhana yang menggambarkan suatu bahasa yang dapat diterima oleh suafu finite Automata. Afuran-afuran yang digunakan untuk merumuskan suatu regular expresion berdasarkan
alphabet I adalah : 1. e adalah sebuah regular expression yang menyatakan himpunan yang mengandung string kosong, ditulis {e}. 2. Jlka a adalah simbol dalam ), maka a adalah regular expression yang menyatakan himpunan dengan string a. ditulis {a} 3. Misalkan r dan s adalah regular expression yang menunjukan bahasa L(r) dan L(s), maka : - (r) I ( s ) adalah regular expressionyangmenunjukanL(r) uL( s) ( r ) ( s ) adalah regular expression yangmenunjukan L( r ) L( s ) - ( r )* adalah regular expression yang menunjukan ( L( r ) )* Suatu bahasa yang ditunjukan oleh regular expression disebut sebagai regular set.JIka ada dua regular expression r dan s menunjukan satu bahasa yang sama maka dapat dikatakanbahwa kedua regular expressionltuequiualent dan ditulis r = s. Beberapa sifat regular expression adalah sebagai berikut :
o r ls=s lr o (r ls) lt=r I (s lt) . (rs)t=r(st) . r(s lt)=rs lrt o
f =f t=f
o r*=(r o r**=r*
I e)*
Vol. 5, No.2, Agustus 2002
9t
.
a
r*=r* I t r+=rr*
4,
FINITE AUTOMATA
Finite Automata adalah suatu model matematika dari sebuah sistem dengan masukan (input) dan keluaran (outpuf) yang pasti dan jelas. Sebuah finite automata terdiri dari sekumpulan state S dan himpunan transisi antar state yang terjadi berdasarkan simbol masukan dari alphabet I. Finite Automata ditunjukan dalam 5 tuple (Q, >,6, %, F) dimana Q adalah himpunan daristate,) adalah himpunan alphabet sebagai masukan, qo adalah state dalamQ yang melambangkan state awal, F adalah himpunan state dalam Q yang menunjukan final state, dan 6 adalah fungsi transisi antar state berdasarkan masukan tertentu, misalkan 6(q, a) adalah transisi untuk setiap state q dengan masukan a.
Finite Automata digambarkan menggunakan graphberurah dimana simpul pada graphberarah melambangkan state.likaada transisi dari state q ke state p berdasarkan masukan a maka akan ada sebuah garis dari state q ke state p dengan lambang a.Dalamfinite automatabisa terjadi transisi tanpa ada suatu simbol masukan yang diberikan. Finite automata ini disebut sebagai Finite Automata with etnoae. Secara umumfinite automata dibedakan menjadi 2 jenis
yaitu:
t. 2.
Non Deterministik Finite Automata Deterministik Finite Automata.
A.
Nondeterministik Finite Automata (NFA)
NFA adalah suatu Finite Automata yang bisa mempunyai 1 atau lebih transisi dari suatu stateke stateyanglain dengan simbol masukan yfrrgsama.
92
Vol. 5, No. 2, Agustus 2002
t-
Diagram Ttansisi untuk NFA
B.
Deterministik Finite Automata (DFA)
DFA adalah suatu Finite Automata yang hanya boleh mempunyai transisi dari satu stateke state laindengan iit ,bol masukan yang sama.
Diagram Transisi untuk DFA
Vol. 5, No.2, Agustus 2002
93
5.
LINGKUNGANPEMROGRAMAN
Simulator Finite Automata (dalam bahasan berikut disingkat SFA) dikembangkan menggunakan bahasa pemrograman Pascal 7.0. Dengan pertimbangan bahwa bahasa pemrograman ini merupakan bahasa yang paling dikuasai oleh anggota tim, dan kemampuan serta fitur bahasa pernrograman ini dapat menunjang kebutuhan penyelesaian masalah. Kegiatan yang telah dilakukan meliputi studi teoritis, analisa dan rancangan program, coding, testing, debuggin9, dan perbaikan program (refining), pengujianberbagai string input, dan analisa performansi simulator. Program dirancang untuk mampu menerima input berupa berbagai jenis atomata, dan untuk setiap automata menerima masukan berupa string yang akan dianalisa apakah termasuk dalam bahasa atau tidak. AHD.PAS adalah program utama yang tertulis dalam s cript bahasa pascal. Program ini merupakan Simulator Finite Automata, membutuhkan beberapa
unit pendukung yaitu unit standar crt dan dos, serta unit tambahan KEYBRD.TPU. COMMAND.COM dan AUTOEXEC.BAT dibutuhkan apabila program ini dijalankan dibawah sistem operasi DOS. AHD.EXE adalah program executable yang diperoleh dari hasil kompilasi AHD.PAS menggunakan kompilator Turbo Pascal 7.0. Simulator Finite Automata ini dikembangkan menggunakan lingkungan pemrograman yang amat sederhana. Perangkat keras yang dibutuhkan minimal menggunakan prosesor Pentium I dengan kecepatan 160 Mhz. Namun unfuk performansi terbaiknya dapat digunakan prosesor dalam kelas yang lebih tirgg misalnya Pentium [V. Memory minimal yang diperlukan cukup 8 Mb, namun untuk performansi yang terbaik dapat digunakan memory yang memiliki kapasitas lebih tinggi hingga mencapai 128 Mb. Hard disk yang digunakan juga minimal hanya berkisar 1 Giga byte, namun untuk performansi terbaik dapat menggunakan Hard disk hingga kapasitas 20 Giga byte.
Perangkat lunak yang dibutuhkan juga amat minimal. Sistem Operasi yang digunakan dapat hanya DOS, dapat juga dibawah Sistem Operasi Windows misalnya Windows 98 ataupun Windows XP. Namun karena program simulator ini berbasis DOS, jika digunakan Operasi Windows harus memanggil shell Command Com. Bahasa pemrograman yang digunakan adalah Turbo Pascal versi 7.0.
94
VoL 5, No. 2, Agustus 2002
I 6.
PENGUII INPVT.OI-ITPUTDAN ANALISA HASIL
Program Simulator Finite Automata memiliki 4 menu utama yaitu File, Edit, Random, dan Quit. File digunakan untuk mengambil deskripsi Automata yang telah disimpan dalam file. Edit digunakan untuk mengedit deskripsi Aut6mata. Hasil eait ini dapat disimpan untuk digunakan kemudian. Random digunakan untuk mer,ggerrerate deskripsi Automata secara random. Hasil geirerasi secara randorrrini juga dapat disimpan untuk digunakan kemudian. Quit digunakan untuk keluar dari program. Selengkapnya menu utama Simulator dapat dilihat dari tampilan layar berikut : Salah satu pilihan yang ada di menu utama File adalah pilihan,untuk memasukan definisi Finite Automata dari File yang telah disimpan :
Definisi FA menyatakan bahasa yang diterima oleh DFA : Suatu slring pada alphabet {a,b} yang tidak memiliki dua buah b atau lebih berturutan.
Vol. 5, No.2, Agustus 2002
95
I
Contoh diatas adalah keluaran dari program Simulator Finite Automata pada Deterministic Finite Automatq yang disimpan dalam file A.AHD untuk mengenali string 'abab' . Output program menyatakan bahwa 'Sukses ! tercapai state akhir dan string hampa', menyatakan bahwa string 'abab' merupakan anggota bahasa yang didefinisikan oleh DFA tersebut. Berikut ini adalah output lain pada AHD yang sama, dengan memasukan
string'abb'.
96
VoL 5, No. 2, Agustus 2002
l Pada keluaran program tersebut, diberikan Pesan 'Gagal ! Tidak Ada Alternatif State Berikut', menyatakan bahwa string yang dianalisa yaifu 'abb' bukan merupakan anggota bahasa yang didefinisikan oleh AHD.
7.
KESIMPULAN
Dari hasil pengembangan Simulator Finite Automata dan percobaan terhadap berbagai language dan string input, dapat disimpulkan beberapa hal berikut : 1,. Simulator Finite Automata yang dikembangkantelah dapat memodelkan perilaku Finite Automaton dalam mengenali dan membangkitkan bahasa sederhana yang termasuk dalam kelas Regular Language. 2. Simulator dapat digunakan sebagai alat Bantu untuk mempelajari teori bahasa dan automata. 3. Simulator dapat digunakan untuk mendukung Perancangan bahasa sederhana, dan merupakan prototype untuk Perancangan bahasa yang lebih kompleks.
8..
SARAN
1.
Adapun saran-saran pengembangan adalah : Kelas bahasa yang diproses dapat ditingkatkan ke kelas yang lebih ting&,
2.
misalnya Context Free Languages, Context Sensitive Languages, sampai Unrestricted Languages. Dalam pengembangan ini, Automata yang dikembangkan bukan lagi Finite Automata biasa melainkan mengarah pada Pushdown Automata maupun Mesin Turing. Memadukan penelitian teoritis ke aspek yang lebih implementatif ,yalttt bagaimana aspek teoritis Finite Automata dapat digunakan untuk mengembangkan kompilator bahasa pemrograman, baik dalam Proses analisa leksikal, analisa sintaksis, maupun analisa semantik'
Vol. 5, No.2, Agustus 2002
97
DAFTARPUSTAKA
1.
[Hop79] Hopcroft, ]ohn E., ]effrey D, Ullman,1979.Intorduction to Automata Theory-Languages, and Computation. Addison Wisley.
2.
[Lew98] Lewis, Harry R.; Christos H. Papadimitriou, 1998. Elements of The Theory of Computation. Prentice Hall, New ]ersey.
3.
lMargTlMartin, ]ohn C, lggT.Introduction to Languages and the theory of Computation. Mc Graw Hill, Singapore.
4.
[Tre85] Tremblay, ]ean Paul; Paul G. Sorensory 1985. The Theory and Practice of Compiler Writing. Mc Graw Hill, Singapore.
5. twilgsl
Wilhelm, Reinhard; Dieter Maurer,L995. Compiler Design.
Addison Wesley.
98
VoL 5, No.2, Agustus 2002
