Finite State Automata (FSA)

Assalamualaikum sobat kreatif Indonesia,

Postingan kali ini yaitu tentang Finite State Automata.

What is it? Cekidot my writing below ---

FINITE STATE AUTOMATA (FSA)

·         FSA didefinisikan sebagai pasangan 5 tupel : (Q, ∑, δ, S, F).

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.

S Î Q : state AWAL

F Ì Q : himpunan state AKHIR

Contoh : FSA untuk mengecek parity ganjil

Q ={Gnp, Gjl}                                                                                                

                                                                     ∑ = {0,1}                                                                                

tabel transisi

δ	0	1
Gnp	Gnp	Gjl
Gjl	Gjl	Gnp

S = Gnp, F = {Gjl}

·         Ada dua jenis FSA :

·               Deterministic finite automata (DFA)

·               Non deterministik finite automata.(NFA)

-       DFA : transisi state FSA akibat pembacaan sebuah simbol bersifat tertentu.

δ  : Q ´ ∑® Q

-       NFA : transisi state FSA akibat pembacaan sebuah simbol bersifat tak tentu

                                            δ : Q ´ ∑ ® 2^Q

DFA :

Q = {q0, q1, q2}        

δ diberikan dalam tabel berikut :

                       

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

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

Kalimat yang dittolak oleh DFA  : bb, abb, abba

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

Contoh :

Telusurilah, apakah kalimat-kalimat berikut diterima DFA di atas :

abababaa   è diterima

aaaabab            è diterima

aaabbaba         è ditolak

Jawab :

i)           δ (q0,abababaa) Þ δ (q0,bababaa) Þ δ (q1,ababaa) Þ

δ (q0,babaa) Þ δ (q1,abaa) Þ δ (q0,baa) Þ δ (q1,aa) Þ

δ (q0,a) Þ q0

   Tracing berakhir di q0 (state AKHIR) Þ kalimat abababaa diterima

ii)         δ (q0, aaaabab) Þδ (q0,aaabab) Þδ (q0,aabab) Þ

δ (q0,abab) Þ δ (q0,bab) Þ δ (q1,ab) Þ δ (q0,b) Þ q1

         Tracing berakhir di q1 (state AKHIR) Þ kalimat aaaababa  diterima

iii)       δ (q0, aaabbaba) Þ δ (q0, aabbaba) Þ δ (q0, abbaba) Þ

δ (q0, bbaba) Þ δ (q1,baba) Þ δ (q2,aba) Þ δ (q2,ba) Þ δ (q2,a) Þq2

         Tracing berakhir di q2 (bukan state AKHIR) Þ kalimat aaabbaba ditolak

Kesimpulan :

sebuah kalimat diterima oleh DFA di atas jika tracingnya berakhir di salah satu state AKHIR.

NFA :

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

Q = {q0, q1, q2,q3, q4}          δ diberikan dalam tabel berikut : 

∑= {a, b,c}

S = q1

F = {q4}

Ilustrasi graf untuk NFA adalah sebagai berikut :

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

Contoh :

Telusurilah, apakah kalimat-kalimat berikut diterima NFA di atas :

 ab, abc, aabc, aabb

Oke deh sekian dulu ya sobat postingan kali ini ..

Salam kreatif :)