TEKNIK OTOMASI BAHASA DAN KOMPILASI study kasus komponen dan jenis Finite State Automata

TEKNIK OTOMASI BAHASA DAN KOMPILASI
study kasus komponen dan jenis Finite State Automata

DISUSUN OLEH :

NAMA          :  ANDI WIJAYANTO

NIM              :   G.211.10.0113

JURUSAN    :   TEKNIK INFORMATIKA

  TEKNIK INFORMATIKA

UNIVERSITAS SEMARANG

                2013

COVER

KATA PENGANTAR..............................................................................        i

DAFTAR ISI..............................................................................................        ii

BAB I

PENDAHULUAN.....................................................................................          1

A.     LATAR BELAKANG ............................................................................          3

B.     MANFAAT DAN TUJUAN ………………………………………….....        3

BAB II

PERMASALAHAN ……………………………………………………..         4

1.      Apakah kompunen dasar yang dimiliki oleh Finite Automata?

2.      Apakah jenis dari Finite State Automata?

BAB III

PEMBAHASAN .......................................................................................        5

BAB 1V

3.1.KESIMPULAN....................................................................................       16

3.2    DAFTAR PUSTAKA………………………………………………      17

KOMPUNEN DAN JENIS FINITE STATE AUTOMATA

BAB I

PENDAHULUAN

1.1 Latar Belakang

Perkembangan zaman yang semakin modern mengubah pola pikir manusia untuk berfikir lebih maju, menciptakan serta mengembangkan berbagai tekhnologi baru, dimana tekhnologi tersebut diciptakan untuk memudahkan kegiatan manusia. Mesin otomatis merupakan salah satu tekhnologi yang sengaja diciptakan untuk mengubah suatu kegiatan yang bersifat manual menuju otomatis dengan tujuan mempercepat proses kegiatan tersebut.

Finite automata adalah mesin abstrak berupa sistem model matematika dengan masukan 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.

Finite State Automata (FSA) adalah model matematika dari sistem dengan masukan dan keluaran berupa nilai diskrit.

Finite State Automata (FSA) merupakan tool yang sangat berguna untuk mengenal dan menangkap pola dalam data. Finite State Automata (FSA) adalah model matematika yang dapat menerima input dan mengeluarkan output yang memiliki state yang berhingga banyaknya dan dapat berpindah dari satu state ke state lainnya berdasarkan input dan fungsi transisi.

Beberapa contoh sistem dengan state berhingga antara lain pada mesin minuman otomatis atau vending machine, pengatur lampu lalulintas dan lexical analyser. Suatu finite automata terdiri dari beberapa bagian Finite automata mempunyai sekumpulan state dan aturan-aturan untuk berpindah dari state yang satu ke state yang lain, tergantung dari simbolnya. Finite automata mempunyai state awal, sekumpulan state dan state akhir. Finite automata merupakan sekumpulan dari lima elemen atau dalam bahasa matematis dapat disebut sebagai 5-tuple. Definisi formal dari finite automata dikatakan bahwa finite automata merupakan list dari 5 kompunen : kumpulan state, input, aturan perpindahan, state awal, dan state akhir.

1.2 Manfaat dan Tujuan

1.2.1 Tujuan

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 dri Teori Bahsa dan Autonata khususnya deterministik finite automata (DFA) dan non-deterministik finite Automata (NFA) dan dapat mengembangkannya sehingga nilai mahasiswa menjadi lebih baik.

1.2.2 Manfaat

1.         Bagi peneliti

Dapat menghasillkan perangkat lunak yang dapat membantu pembelajaran mata kulaih teori bahasa dan autonata, dan dapat meningkatkan perkembangan studi finie state automata di Indonesia, dapat mengembangkan diri dalam hal isi dari Teori Bahsa dan Autonata, khususnya determnistik finite Automata (DFA) dan non deterministik finite automata (NFA).

2.         Bagi Mahasiswa

Lebih mengerrti dalam mengerjakan tugas-tugas UTS, maupun USA 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.

BAB II

PERMASALAHAN

3.      Apakah kompunen dasar yang dimiliki oleh Finite Automata?

4.      Apakah jenis dari Finite State Automata?

BAB III

PEMBAHASAN

1.      Apakah kompunen dasar yang dimiliki oleh Finite Automata?

Komponen dasar yang dimiliki oleh Finite Automata adalah Alphabet yaitu himpunan symbol/lambang yang dikenali. Himpunan Alfabet diwakili dengan  ∑ jika dan hanya jika ∑ merupakan himpunan symbol yang bersifat tetap dan bukan merupakan himpunan kosong.

Contoh umum dari Alphabet adalah 26 (dua puluh enam) huruf yang dikenali dalam bahasa Indonesia ataupun rangkaian karakter ASCII, yang merupakan rangkaian standar dari kode-

 kode komputer.

Sedangkan sebuah word, yang disebutkan juga string atau sentence adalah rangkaian  satu atau lebih alphabet yang telah dinyatakan sebelumnya. Rangkaian word itu sendiri disebut bahasa (language), yang diwakili dengan L.

Berikut ini adalah contoh Alphabet beserta words yang dapatdibentuknya:

• ∑ = {a, b}, makacontoh words yang dapatdibentuknyayaitu“aab”, “abab”, “a”, “bbbbbb”, dan lain- lain.
• ∑ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, maka contoh words yang dapat dibentuknya yaitu “26498098”, “100103”, “0000”, dan lain- lain.

Lebih lanjut, Concatenation adalah proses menggabungkan dua buar words menjadi satu word baru, yaitu terdiri dari rangkaian alphabet dari word pertama dan disambung dengan rangkaian alphabet dari word ke dua.

Ø  ∑ = {a, b}, words = “aaa” dan y = “bbb”dimana setiap a merupakan anggota himpunan ∑, a ∈ ∑  dansetiap b anggota himpunan ∑, b ∈ ∑.  Maka, gabungan atau concatenation x dan y, dinyatakan dengan x,y = “aaabbb”.

Setelah memiliki pemahaman diatas, maka definisi dari sebuah Finite Automata dapat ditetapkan sebagai suatu model Matematis dari sebuah mesin yang menerima suatu rangkaian words tertentu yang mengandung alphabet ∑.

Setiap FSA memiliki:

1.      Himpunanberhingga (finite) status (state):

Ø  Satu buah status sebagai status awal (initial state), biasa dinyatakan  q0.

Ø  Beberapa buah status sebagai status akhir (final state).

2.      Himpunan berhingga symbol masukan.

3.      Fungsi transisi:

Ø  Menentukan status berikutnya darisetiap pasang status dan sebuah symbol masukan.

FSA didefinisikan sebagai pasangan 5 Tupel/ Komponen M = ( Q, ∑, δ, S, F ) :

Ø  M : Nama Mesin.

Ø  Q : Himpunan hingga state/ kedudukan.

Ø  ∑ :  Himpunan hingga simbol input/ masukan (alfabet).

Ø  Δ : Fungsi transisi, berbentuk δ (qi, a) = qk

Ø  S : State AWAL (Start) / kedudukanawal, S -> Q.

Ø  F : Himpunan state AKHIR (Final), F -> Q.

Contoh : FSA untuk mengecek parity ganjil.

Q ={Gnp, Gjl} himpunan state .

∑ ={0,1} himpunan simbol input.

δ = fungsi transisi,

S = Gnp (Start).

F = {Gjl} (Final) himpunan state AKHIR.

       (Ingat untuk himpunan harus ditulis di dalam{}).

Dari diagram tersebut Contoh Bahasa /L(m) yang diterima adalah :

0110   = Karena state akhirnya adalah finalnya state, dalam konteks ini adalah Gjl.

1011  = Diterima.

0100  = Diterima.

11110 =Diterima.

011   = Ditolak (karena state akhirnya tidak di final state, Gnp).

11011 = Ditolak.

Secara visual, suatu bagan Finite Automata diwakili dengan suatu graf berarah dengan rumus G = <V, E> ; dimana V = S dan E = { | s,t S, a ∑_^(s,a) =  t }

“V” merupakan himpunan verteks pada graf, “E” merupakan himpunan sisi pada graf yang pada dasarnya merupakan fungsi- fungsi transisi antara state yang satu ke state yang lain (state “s” dan “t”, yang masing- masingnya merupakan anggota dari “S”). Selain itu, setiap sisi graf diberi nama dengan alphabet penghubung (alphabet “a”) antara dua verteks yang dihubungkannya.

Pada umumnya dalam suatu bagan Finite Automata terdapat minimal satu state akhir.Verteks graf yang menunjukkan suatu state, tetapi bukan state akhir, dinyatakan dengan lingkaran, sedangkan yang menunjukkan suatu state akhir dinyatakan dengan lingkaran ganda, sisi graf yang menunjukkan fungsi transisi dinyatakan dengan tanda panah.

Jadi suatu state dapat menjadi asal dan tujuan dalam suatu fungsi transisi yang melibatkan dua buah state. Ditinjau dari sudut pandang state asal, maka setiap state (kecuali state akhir) pasti menjadi state asal dan memiliki fungsi transisi ke state yang lain, sedangkan state akhir dapat tidak memiliki fungsi transisi state ke yang lain. Ditinjau dari sudut pandang state tujuan, maka setiap state (kecuali state awal) pasti menjadi pasti state tujuan.

2.      Apakah jenis dari Finite State Automata?

FSA dibedakan menjadi dua macam, yaitu :

Ø  Deterministic Finite Automata (DFA).

Transisi state FSA akibat pembacaan sebuah simbol bersifat tertentu.

Ø  Non-Deterministik Finite Automata (NDFA).

Transisi state FSA akibat pembacaan sebuah simbol bersifat tak tentu.

Jenis FSA:

Ø  DFA (Deterministic Finite Automata) :

-        Atomata berhingga yang pasti (tetap/tertentu).

-        Setiap rancangan state input selalu tepat ada satu state berikutnya.

-        Dari suatu state ada tepat satu state berikutnya untuk setiap symbol masukan yang diterima.

-        Untuk sebuah state dan input yang berlaku bias ditentukan tepat satu state berikutnya.

-        Suatu string x dinyatakan diterima bila_(S,x) berada pad state akhir.

Dengan kata lain secara formal bila M adalah sebuah bahasa FSA, M = (Q, _, d, S, F) menerima bahasa yang disebut L(M) yangmerupakanhimpunan {x | d (S,x) di dalam F}.

Ø  NDFA (Non-Deterministic Finite Automata) :

-        Atomata berhingga yang tidak pasti.

-        Untuk setiap pasangan state input, bias memiliki 0 (nol) atau lebih pilihan untuk state berikutnya.

-        Untuk setiap state tidak selalu tepat ada satu state berikutnya untuk setiap simbol input yang ada.

-        Dari suatu state bias terdapat 0,1 atau lebih busur keluar (transisi) berlabel simbol input yang sama.

-        Untuk NFA harus dicoba semua kemungkinan yang ada sampai terdapat satu yang mencapai state akhir.

-        Suatu string x dinyatakan diterima oleh bahasa NFA, M= (Q, _, d, S, F) bila {x | d (S,x) memuat sebuah state di dalam F}.

Ø   (DFA)Deterministic Finite Automata:

ContohDFA:

DFA :

Q={q0,q1,q2}
δ  diberikan dalam table berikut :

∑={a,b}
S=q0
F={q0,q1}

Kalimat yang diterima oleh DFA : a, b, aa, ab, ba, aba, bab, abab, baba.

Kalimat yang ditolak oleh DFA : bb, abb, abba.

DFA ini menerima semua kalimat yang tersusun dari symbol a dan b yang tidak mengandung substring  bb.

DFA :

Pada suatu NFA, Suatu state dapat memiliki tujuan ke beberapa state yang berbeda dengan alphabet penghubung yang sama. Akan tetapi, hal ini tidak diperbolehkan pada suatu DFA. Untuk menyederhanakan suatu NFA menjadi suatu DFA dipergunakan Tabel Transisi yang memiliki kolom berupa variasi alphabet yang diterima dan baris berupa nama- nama state asal. Sedangkan titik temu antara suatu kolom dan baris diisi dengan nama- nama state tujuan dari state asal yang tertera pada bagian kolom.

Berikut ini adalah Contoh suatu DFA yang akan mengenali suatu bilangan Cacah:

DFA bilanganCacah = <, S, S₀, F>

   ={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

S   ={S_0, S₁, S₂}

S₀=S₀

F   ={S₁, S₂}

Bagan DFA untuk Bilangan Cacah:

Table Transisi DFA untuk Bilangan Cacah:

	0	1..9
S0	S1	S2
S1	-	-
S2	S2	S2

Bagan pada Gambar di atas sudah merupakan bagan DFA karena tidak ada state asal yang memiliki tujuan kelebih dari satu state tujuan dengan alphabet penghubungan yang sama.

Ø  (NFA) Non-deterministik Finite Automata:

Pada NFA terdapat kemungkinan lebih dari 1 transisi yang keluar dari sebuah state dengan sumber input yang sama.

Gambar berikut ini  adalah Contoh NFA yang menginformasikan  NFA yang menerimaaa* | bb*:

Table Transisi NFA Seperti :

		a	B
0	1,3	-	-
1	-	2	-
2	-	2	-
3	-	-	4
4	-	-	4

Bagan pada gambar itu sudah merupakan bagan NFA, karena ada state asal yang memiliki tujuan ke lebih dari satu state tujuan dengan alphabet penghubungan yang sama ( ).

Pada gambar diatas state 0 sebagai start dan state 2 serta state 4 adalah final state. Disini digambarkan NFA menerima suatu input berupaaa* | bb*. Suatu string “aaa” akan diterima dengan melalui state 0, 3, 4, 4, 4 dan 4.  NFA  mempunyai kelebihan dapat melakukan backtracking,  namun aksesnya lebih  lambat dibandingkan dengan DFA (Deterministic Finite Automaton).

NFA
Contoh NFA:

Berikut ini sebuah contoh NFA (Q, ∑, δ, S, F).

dimana:
Q={q0,q1,21,q3,q4}
∑={a,b,c}
S=q0
F = {q4}

Kalimat yang diterima NFA di atas : aa, bb, cc, aaa, abb, bcc, cbb
Kalimat yang tidak diterima NFA di atas : a, b, c, ab, ba, ac, bc

Sebuah kalimat di terima NFA jika :

·                Salah satu tracing-nya berakhir di state AKHIR, atau

·                Himpunan state setelah membaca string tersebut mengandung state AKHIR.

Implementasi Finite Automata.

Sistemdengan state berhinggaditerapkanpada:

-        Sistem elevator.

-        Mesin pengeluar minuman kaleng (vending machine).

-        Pengatur lampu lalulintas (traffic light regulator).

-        Sirkuit penyaklaran (switching) di computer dan telekomunikasi.

-        Protokol komunikasi (communication protocol).

-        Analisis Leksikal (Lexical analyzer).

-        Neuron nets.

-        Sistem Komputer.

Finite State Diagram (FSD).

Finite State Automata dapat dimodelkan dengan Finite State Diagram (FSD) dapat juga disebut State Transition Diagram.

Finite State Diagram terdiridari:

1.      Lingkaran menyatakan state.

Lingkaran diberi label sesuai dengan nama state tersebut.

Adapun pembagian lingkaran adalah:

- Lingkaran bergaris tunggal berarti state sementara.

- Lingkaran bergaris ganda berarti state akhir.

2.      Anak Panah menyatakan transisi yang terjadi.

Label di anak panah menyatakan simbol yang membuat transisi dari 1 state ke state lain. Satu anak panah diberi label start untuk menyatakan awal mula transisi dilakukan.

BAB IV

KESIMPULAN

Klasifikasi FSA dibedakan menjadi dua jenis yaitu :

       I.            (DFA) Deterministic Finite Automata.

Terdiridari 1 transisidarisuatu state pada 1 simbolmasukan.

    II.            (NFA) Non-DeterministikFinite Automata.

Terdirilebihdari 1 transisidarisuatu state dimungkinkanpadasimbolmasukan yang sama.

Kedua Finite Automata tersebut mampu mengenali himpunan reguler secara presis. Dengan demikian kedua Finite Automata itu dapat mengenali string-string yang ditunjukkan dengan ekspresi reguler secara tepat.

DFA dapat menuntun recognizer (pengenal) lebihcepat dibanding NDFA.

Namun demikian, DFA berukuran lebih besar dibanding NDFA yang ekivalen dengannya. Lebih mudah membangun NDFA dibanding DFA untuk suatu bahasa, namun lebih mudah mengimplementasikan DFA dibanding NDFA.

DAFTAR PUSTAKA

Danang Junaedi, Finite State Automata, IF Utama – Semarang, 2009

Rizky Endah Melli, Penerapan Konsep Fonote State Automata, Jurnal Komputasi – Universitas Lampung 2012

Anung Final, Pengenalan Suku Bahsa Indoensia menggunakan Finite State Automata, Unpar - 2011