FINITE STATE AUTOMATA
(FSA)
|
Kelas Bahasa
|
Mesin Pengenal Bahasa
|
|
Regular Grammar, RG
|
|
Ø
Grammar tipe ke-3 : Regular Grammar (RG)
Ciri :aÎ V
, bÎ {V
, VV} atau aÎ V, bÎ {V, VV}
, 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
·
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 ´ ∑ ® 2Q
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
}
, 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}
,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)
,abc) Þδ(q,bc) Èδ(q ,bc) Þ {δ(q,c) Èδ(q,c)}Èδ(q, c)
{{ q, q}È{ q}}È{ q} = {q, q, q,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)} È
,aabc) Þδ(q,abc) Èδ(q ,abc)Þ{δ(q,bc) Èδ(q ,bc)} È
δ (q ,bc)Þ{{δ(q, c) Èδ(q,c)} Èδ(q, c)} Èδ(q, c)Þ
,bc)Þ{{δ(q, c) Èδ(q,c)} Èδ(q, c)} Èδ(q, c)Þ
{{{ q, q}È { q}} È {q}} È {q} = {q, q, q,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)
,aabb) Þδ(q,abb) Èδ(q ,abb)
Þ{δ(q,bb) Èδ(q ,bb)} Èδ (q ,bb)
,bb) Èδ(q ,bb)} Èδ (q ,bb)
Þ{{δ(q, b) Èδ(q,b)} Èδ(q, b)} Èδ(q, b)
, b) Èδ(q,b)} Èδ(q, b)} Èδ(q, b)
Þ{{{ q, q}È { q, q}} È {q}} È {q} = {q, q, q, q}
, q}È { q, q}} È {q}} È {q} = {q, q, q, q}
Himpunan
state mengandung state AKHIR Þkalimat aabb diterima
Download disini
