Tugas teknik kompilasi ( Penjelasan Finite State Automata / FSA, Contoh soal DFA dan NFA)

FINITE STATE AUTOMATA (FSA)

Kelas Bahasa	Mesin Pengenal Bahasa
Regular Grammar, RG	Finite State Automata, FSA

Ø Grammar tipe ke-3 : Regular Grammar (RG)

Ciri :aÎ V, bÎ {V, VV} atau aÎ V, bÎ {V, VV}

Ø 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 : FSAuntukmengecek parity ganjil

Q ={Gnp, Gjl}                               diagram transisi

∑ = {0,1}

tabeltransisi

δ	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 symbol 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, apakahkalimat-kalimatberikutditerima 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 = {q, q, q,q, q}          

δ diberikan dalam tabel berikut :

∑= {a, b,c}	δ	a	b	c
S = q	q	{q, q}	{q, q}	{q, q}
F = {q}	q	{q, q}	{q}	{q}
	q	{q}	{q, q}	{q}
	q	{q}	{q}	{q, q}
	q	Æ	Æ	Æ

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

Jawab :

1. δ(q,ab) Þδ(q,b) Èδ(q ,b) Þ {q, q} È {q} = {q, q, q}

Himpunan state TIDAK mengandung state AKHIR Þkalimat ab tidak diterima

2. δ(q,abc) Þδ(q,bc) Èδ(q ,bc) Þ {δ(q,c) Èδ(q,c)}Èδ(q, c)

{{ q, q}È{ q}}È{ q} = {q, q, q,q}

Himpunan state TIDAK mengandung state AKHIR Þkalimatabctidakditerima

3. δ(q,aabc) Þδ(q,abc) Èδ(q ,abc)Þ{δ(q,bc) Èδ(q ,bc)} È

δ (q ,bc)Þ{{δ(q, c) Èδ(q,c)} Èδ(q, c)} Èδ(q, c)Þ

{{{ q, q}È { q}} È {q}} È {q} = {q, q, q,q}

Himpunan state TIDAK mengandung state AKHIR Þkalimat aabc tidak diterima

4. δ(q,aabb) Þδ(q,abb) Èδ(q ,abb)

Þ{δ(q,bb) Èδ(q ,bb)} Èδ (q ,bb)

     Þ{{δ(q, b) Èδ(q,b)} Èδ(q, b)} Èδ(q, b)

Þ{{{ q, q}È { q, q}} È {q}} È {q} = {q, q, q, q}

Himpunan state mengandung state AKHIR Þkalimat aabb diterima

 Download disini