Finite State Automata & Grammar

1. Finite State Automata (FSA)

Finite State Automata (FSA) adalah model matematika yang dapat menerima input dan mengeluarkan output yang memiliki state yang berhingga banyaknya dan dapat berpindah dari satu state ke state lainnya berdasarkan input dan fungsi transisi. Finite state automata tidak memiliki tempat penyimpanan/memory, hanya bisa mengingat state terkini.
Finite State Automata dinyatakan oleh pasangan 5 tuple, yaitu:

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 :

Definisi :

M=(Q , Σ , δ , S , F )
Q = {Q0, Q1, Q2, Q3, Q4}
Σ = {0, 1}
S = {q0}
F=  {q2}
δ = Transition Function

Berikut adalah hasil uji input dengan Multiple Run (JFLAP) :

2. Grammar

Grammar G didefinisikan sebagai pasangan 4 tuple: V_t, V_n, S, dan P, dan dituliskan sebagai G(V_t, V_n, S, P), dimana:
V_t : himpunan simbol-simbol terminal (alfabet) = kamus V_n : himpunan simbol-simbol non terminal S C V : simbol awal (atau simbol start) P : himpunan produksi.

Contoh :

Definisi :

G = (V, T, P ,S)
V = {S, A, B, C, D}
T = {0, 1, 2, 3}
P = {S→0, S→2C, S→1B, D→1A, C→1, B→2D, D→2A, A→D, A→3}
S = {S}

Berikut adalah hasil uji input dengan Multiple Run (JFLAP) :