Finite State Automaton

Secara umum representasi scanner dinyatakan dengan menyusun suatu diagram transisi atau transition diagram yang disebut finite automaton.

Finite Automaton memiliki konsep sebagai bentuk paling sederhana dari peralatan komputerisasi abstrak. Finite- state control dari suatu finite automaton juga merupakan inti dari begitu banyak peralatan komputer yang kompleks.

Pengaplikasian finite automata dapat ditemukan pada algoritma- algoritma yang digunakan untuk pencocokkan string pada perangkat lunak editor teks dan perangkat lunak pengecekan ejaan, serta dapat ditemui juga pada penganalisa sintaks yang digunakan oleh assemblers atau compilers. 

Automaton memiliki suatu alur khusus dan unik untuk setiap kata yang akan dikenali atau diterima. Jika suatu alur berakhir pada suatu state yang disebut sebagai final state atau accepting state, maka kata yang ditelusuri tersebut dikatakan dikenali oleh automaton.

Komponen dasar yang dimiliki ileh Finite Automaton 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 dapat dibentuknya:

• ∑ = {a, b}, maka contoh words yang dapat dibentuknya yaitu “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 buah 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 ∈ ∑  dan setiap 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 Automaton dapat ditetapkan sebagai suatu model matematis dari sebuah mesin yang menerima suatu rangkaian words tertentu yang mengandung alphabet ∑. Finite Automaton memiliki lima komponen, yaitu antara lain:

1. ∑ merupakan himpunan alphabet input (himpunan simbol/ lambang yang tetap dan bukan merupakan himpunan kosong)
2. S, merupakann himpunan state yang tetap dan bukan merupakan himpunan kosong.
3. S0, merupakan state awal (start state atau initial state), merupakan anggota dari S.
4. d, merupakan fungsi transisi antar state; d: S x ∑® S.
5. F, merupakan himpunan state akhir (final state atau accepting state), merupakan sub-himpunan dari S.

Secara visual, suatu bagan Finite Automaton diwakili dengan suatu graf berarah dengan rumus G= < V , E > ; dimana  V = S  dan E =  { | s,t Î S, a Î∑_^d(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 Automaton terdapat minima 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.

Finite automaton dibedakan menjadi dua macam, yaitu:Finite automaton dibedakan menjadi dua macam, yaitu:

• NFA (Nondeterministic Finite Automaton)

Pada NFA terdapat kemungkinan lebih dari 1 transisi yang keluar dari sebuah state dengan sumber input yang sama. GAmbar ini  adalah contoh NFA yang menginformasikan  NFA yang menerima aa* | bb*:

tabel yang  transisi NFA seperti :

d	l	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 (l ).

Pada gambar diatas state 0 sebagai start dan state 2 serta state 4 adalah final state. Disini digambarkan NFA menerima suatu input berupa aa* | 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).

• DFA (Deterministic Finite Automaton)

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 bilangan cacah = <å, 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:

d	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 ke lebih dari satu state tujuan dengan alphabet penghubungan yang sama.

refferensi :

*Copcroft, John E., and Rajeev Motwani, Jeffrey D. Ullman, "Introduction to Automata Theory, Languages, and Computation"- 2nd edition, Addison  Wesley, 2001.

*Hariyanto, Bambang, Ir., MT, "Teori Bahasa, Otomata dan Komputasi serta Terapannya", Cetakan Pertama, Informatika Bandung 2004.

*Kelly, Dean, "Otomata dan Bahasa-Bahasa Formal" : Suatu Pengantar, Judul Asli Automata and Formal Languages : An Introduction, Edisi Asli Prentice Hall,Inc 1995. Alih Bahasa Yozep Edyanto, Edisi Indonesia, PT Prenhallindo Jakarta 1999.