TBO

FINITE STATE AUTOMATA

Dine Tiara Kusuma

FINITE STATE AUTOMATA

FSA (Finite State Automata)

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

Dine Tiara Kusuma

 FSA atau AH (Automata Hingga) didefinisikan
sebagai pasangan 5 tupel → M = (Q, ∑, δ, S, F).

Q : himpunan hingga state

FINITE STATE
∑ : himpunan hingga simbol input (alfabet)
AUTOMATA
δ : 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
Dine Tiara Kusuma
FINITE STATE AUTOMATA

• Mesin ini memiliki 6 state

: (q0,q1,q2,q3,q4,q5).
• State awal q0,
• Sedangkan q3 dan q4
adalah state akhir, dan
• Simbol input adalah
(a,d,u)

Dine Tiara Kusuma

 • Tabel Transisi
CONTOH FINITE δ 0 1
STATE AUTOMATA * Gnp Gnp Gjl

→ Gjl Gjl Gnp

• Contoh : FSA untuk
mengecek parity ganjil
• Diagram Transisi
• Q ={Gnp, Gjl}
• ∑ = {0,1}
• S = Gnp
• F = Gjl

Dine Tiara Kusuma

 Definisi M = (Q,Σ,δ,S,F) di mana :
Q = himpunan state
Formal FSA
Σ = abjad, himpunan simbol
input/masukan
δ = fungsi transisi, δ : Q x Σ → Q
S = state awal / initial state
F = himpunan state akhir/final state
Dine Tiara Kusuma
FSA Terbagi 2:

Deterministic (DFA)

Non deterministic (NFA)

Dine Tiara Kusuma
 Deterministik (DFSA/DFA)
• Pada setiap input, hanya ada satu
keadaan (state) tujuan dari
Jenis FSA keadaan saat ini.
Non - Deterministik
(NFSA/NFA)
• Pada setiap input terdapat lebih
dari satu keadaan tujuan dari
keadaan saat ini.
Dine Tiara Kusuma
DETERMINISTIC
FINITE AUTOMATA
(DFA)
DFA, terdiri atas 5 tuple, yaitu :
A = (Q, , , q0, F)

Dine Tiara Kusuma

 1. Diagram Transisi / State Diagram
• Tiap keadaan merupakan simpul
Notasi Lain DFA • Tiap keadaan q  Q dan tiap simbol a  ,
dituliskan sebagai (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
2. 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)
Dine Tiara Kusuma
 ■ State Diagram
CONTOH DFA
• Contoh DFA yang dapat
menerima string
berakhiran 01
• A = ({q0, q1, q2}, {0,1}, ,  0 1
q0, {q2}) dengan fungsi → q0 q2 q0
transisi  diberikan
q1 q1 q2
dalam bentuk table :
* q2 q2 q2
Dine Tiara Kusuma
CONTOH DFA 1 : Jika M diberi input
aabba, dengan state awal
•M = (Q, , , s, F), dimana : (q0, aabba), maka :
• Q = {q0, q1}, (q0,aabba)
├M (q0,abba)
•  = {a,b}, a
Diagram State
├M (q0,bba)
a
• S = q0, ├M (q1,ba)
• F = {q0} q0
b
q1 ├M (q0,a)
Tabel Transisi b ├M (q0,e)
Karena (q0,aabba)
 a b
├*M (q0,e), jadi aabba
q0 q0 q1 diterima oleh M
q1 q1 q0 Dine Tiara Kusuma
CONTOH DFA 2 : Contoh : diberikan input pada
mesin DFA 110111, lakukan
tracer :
1 1 (q0,110111)
├M (q0,10111)
q0
0
q1
0
q2 ├M (q0,0111)
├M (q1,111)
├M (q1,11)
├M (q1,1)
├M (q1,e)
Karena berhenti bukan di q2,
maka 110111 tidak diterima
oleh mesin DFA
Dine Tiara Kusuma
CONTOH DFA 3 : Contoh : diberikan input
pada mesin DFSA 10110,
1 1 lakukan tracer :
(q0,10110)
0 0 ├M (q0,0110)
q0 q1 q2
├M (q1,110)
├M (q1,10)
├M (q1,0)
├M (q2,e)
Karena berhenti di q2,
maka 10110 diterima
Dine Tiara Kusuma
oleh mesin DFSA
 Tabel Transisi

CONTOH DFA 4 : d
q0
0
q2
1
q1
DFA nya : Contoh : diberikan string q1 q3 q0
Q = {q0 , q1 , q2 , q3 } 011 dan 1010, buktikan q2 q0 q3
 = {0,1} bahwa string tersebut q3 q1 q2
S = q0 diterima atau ditolak !
F = { q 0} State Diagram

(q0,011) = (q2,11) =
(q3,1) = q2 Ditolak

(q0,1010) = (q1,010)
= (q3,10)
=(q2,0)
= (q0,e) Diterima
Dine Tiara Kusuma
CONTOH DFA 5 : δ 0 1
STRING INPUT :
a b d - 11010
• Σ = {0,1} - 11100
b c d
• Q = {a, b, c, d} - 11111
c d c - 00001
• S = {a} - 00110
d a b
• F = {b, c}
• Fungsi transisi δ : Q x Σ → Q, yang didefinisikan sebagai :
δ = {((a,0),b), ((a,1),d), ((b,0),c), ((b,1),d), ((c,0),d), ((c,1),c), ((d,0),a),
((d,1),b)}
• Fungsi transisi dapat ditulis dalam bentuk tabel

DIAGRAM TRANSISI
?
Dine Tiara Kusuma