Finite State Automata atau FSA - Tata Bahasa dan Automata

FSA atau Finite State Automata adalah tool yang sangat berguna dalam perancangan lexical analyzer, yaitu bagian dari kompilator yang mengelompokkan karakter - karakter ke dalam sebuah token, yang berupa unit terkecil seperti nama, variabel, dan keyword. FSA dipakai untuk penganalisa leksikal dan dipakai juga dalam text editor, pemrosesan teks, dan program file-searching.

FSA atau AH (Automata Hingga) didefinisikan sebagai pasangan 5 tupel :

Q : Himpunan hingga state

∑ : himpunan hingga simbol input (alfabet)

δ : fungsi transisi, menggambarkan transisi state FSA akibat pembacaan simbol input.

fungsi transisi ini biasanya diberikan dalam bentuk tabel.

mesin ini memiliki 6 state : (q0, q1, q2, q3, q4, q5).

state awal q0

sedangkan q3 dan a4 adalah state akhir, dan simbol input adalah (a,d,u).

Contoh Finite State Automata

diagram transisi :

contoh : FSA untuk mengecek parity ganjil

Q = {gnp, gjl}

∑ = {0,1}

S = gnp

F = gjl

Definisi Formal FSA

M = (Q, ∑, δ, S, F) dimana :

Q = himpunan state

∑ = abjad, himpunan simbol input/masukan

δ = fungsi transisi, δ : Q x ∑ -> Q

S = state awal / initial state

F = himpunan state akhir/final state

FSA terbagi 2 :

Non Deterministic (NFA/NFSA) :

merupakan istilah pada setiap input terdapat lebih dari satu keadaan tujuan dari keadaan saat ini.

Deterministic (DFA/DSFA) :

merupakan istilah pada setiap input, hanya ada satu keadaan (state) tujuan dari keadaan saat ini.

terdiri atas 5 Tuple, yaitu : A = (Q, ∑, δ, q0, F)

notasi lain DFA :

1. Diagram transsi/state diagram

- tiap keadaan merupakan simpul

- δ(q,a) = p artinya diagram transisi memiliki panah dari q ke p, yang berlabel a

- keadaan awal (q0) ditandai dengan adanya panah tanpa sumber

- simpul yang menjadi keadaan final ditandai dengan lingkaran bergaris tepi ganda

1. tabel transisi

- representasi daftar dari suatu fungsi

- baris menunjukkan keadaan dan kolom menunjukkan input

- isi dari baris menunjukkan keadaan q dan isi dari kolom input a menunjukkan keadaan δ(q,a)

contoh DFA :

M = (Q, ∑, δ, S, F) dimana :

Q = {q0, q1}

∑ = {a,b}

S = q0

F = {q0}

jika M diberi input aabba, dengan state awal (q0, aabba), maka :

maka aabba diterima oleh M.

contoh :

DFAnya :

Q = {q0, q1,q2,q3}

∑ = {0,1}

S = q0

F = {q0}

soalnya : buktikan bahwa string tersebut diterima atau ditolak

δ(qo,011) = δ(q2,11) = δ(q3,1) = q2 ditolak

δ(q0,1010) = δ(q1,010) = δ(q3,10) = δ(q2,0) = δ(q0,e) diterima