- Model matematika yang dapat menerima input dan mengeluarkan output
- Memiliki state yang berhingga banyaknya dan dapat berpindah dari satu state ke state lainnya berdasar input dan fungsi transisi
- Tidak memiliki tempat penyimpanan/memory, hanya bisa mengingat state terkini.
- Mekanisme kerja dapat diaplikasikan pada : elevator, text editor, analisa leksikal, pencek parity.
0
|
1
|
0
|
1
|
1
|
0
|
1
|
FA |
Contoh pencek parity ganjil :
Misal input : 1101
Genap 1 Ganjil 1 Genap 0 Genap 1 Ganjil
diterima mesin
Misal input : 1100
Genap 1 Ganjil 1 Genap 0 Genap 0 Genap
ditolak mesin
Def 1. Finite State Automata dinyatakan oleh 5 tuple
M=(Q , Σ , δ , S , F )
Q = himpunan state
Σ = himpunan simbol input
δ = fungsi transisi δ : Q × Î£
S = state awal / initial state , S ∈ Q
F = state akhir, F ⊆ Q
Contoh diatas,
Q = {Genap, Ganjil}
Σ = {0,1}
S = Genap
F = {Ganjil }
δ
|
0
|
1
|
Genap | Genap | Ganjil |
Ganjil | Ganjil | Genap |
atau
δ(Genap,0) = Genap
δ(Genap,1) = Ganjil
δ(Ganjil,0) = Ganjil
δ(Ganjil,1) = Genap
Jenis FSA
Deterministic Finite Automata (DFA) : dari suatu state ada tepat satu state berikutnya untuk setiap simbol masukan yang diterima
Non-deterministic Finite Automata (NFA) : dari suatu state ada 0, 1 atau lebih state berikutnya untuk setiap simbol masukan yang diterima
Deterministic Finite Automata
- Contoh : pengujian parity ganjil.
- Contoh lain : Pengujian untuk menerima bit string dengan banyaknya 0 genap,
serta banyaknya 1 genap.
♦ 0011 : diterima.
♦ 10010 : ditolak, karena banyaknya 0 ganjil - Diagram transisi-nya :
- DFA nya
Q = {q0 , q1 , q2 , q3 }
Σ = {0,1}
S = q0
F = { q0}
fungsi transisi
δ
|
0
|
1
|
q0 | q2 | q1 |
q1 | q3 | q0 |
q2 | q0 | q3 |
q3 | q1 | q2 |
- Contoh lain DFA : Variabel dalam bahasa pascal diawali oleh huruf (besar/kecil),
dan diikuti dengan huruf atau angka.
- Contoh DFA lainnya :