Fine State Automata

Finite State Automata (FSA)

Finite State Automata (FSA) adalah mesin abstrak berupa sistem model matematika dengan masukan dan keluaran diskrit yang dapat mengenali bahasa paling sederhana (bahasa reguler) dan dapat diimplementasikan secara nyata.

Bahasa yang paling sederhana adalah bahasa reguler (tipe 3). Mesin yang bisa mengenalinya adalah Finite Automata. Finite Automata adalah mesin komputasi. Pada bahasan ini mesin komputasi yang dimaksud adalah mesin abstrak bukan mesin fisik, namun memadai untuk diimplementasikan secara nyata.

DEFINISI SECARA FORMAL

Secara formal FSA dinyatakan dengan 5-tuple atau M =(Q, Σ, δ, q₀, F):

1. Q = himpunan state/kedudukan

2. Σ = abjad, himpunan simbol input

3. δ = transition function

4. q₀ ∈ Q = start state

5. F ⊆ Q = set of accept (or final) states

DEFINISI SECARA FORMAL

v  Gambar di atas disebut diagram keadaan M1

v  Ia memiliki empat status, berlabel q0,q1, q2, dan q3

v  Status awal, q0, ditunjukkan oleh panah yang menunjuknya entah dari mana

v  Status terima, q0, adalah negara dengan lingkaran ganda

v  Panah yang berpindah dari satu kondisi ke kondisi lain disebut transisi

Contoh fsa

Kita dapat menggambarkan secara formal dengan menulis M1 = (Q, Σ, δ, q0, F)), di mana:

1. Q=  {q0,q₁, q₂, q₃}
2. Σ = {0, 1}
3. δ digambarkan sebagai :
4. q0 adalah kondisi awal, dan
5. F = {q0}

	0	1
Q0	Q2	Q1
Q1	Q3	Q0
Q2	Q0	Q3
Q3	Q1	Q2

-          Uji Input Step With Closure

1101

Ditolak

-          Uji Input Step By Step

0101

Diterima

-          Uji Input Fast Run

1001

Diterima

-          Uji Input Multiple Run

1110

Direject