Teori Bahasa dan Otomata

Finite State Automata memiliki state yang banyaknya tak terhingga dan dapat berpindah dari satu state ke state yang lain.
Finite State Automata dinyatakan oleh 5 tupel atau
M = ( Q , Σ , δ , S , F ) 
Q = Himpunan state
Σ = Himpunan symbol input
δ = Fungsi transisi
S = State awal
F = Himpunan state akhir

Contoh 

Deskripsi
M1 = ( Q , Σ , δ , S , F )
Q = { q0 , q1 , q2 , q3 , q4 }
Σ = { 0 , 1 }
S = { q0 }
F = { q4 }
δ =

Dilakukan Pengujian dengan Input:
1111      Accept
111001 Accept

11011  Accept

111     Accept

1101001 Accept

Grammer

Grammar adalah himpunan dari aturan-aturan yang terstruktur yang mengatur susunan kalimat, frase, dan kata dalam bahasa apapun

Tata Bahasa Grammar didefinisikan dalam 4 tupel D = ({ V,T,P,S })
V = Himpunan symbol variable
T = Himpunan symbol terminal
P = Kumpulan aturan produksi
S = Simbol awal

Pengujian Input

rssr =accept

rsrrsr=accept

a-> rB

B->rC

b->sE

C->sQ

D->rH

D->sG

H->sG-E->rD

E->sF

F->r

G->r

V={A,B,C,D,E,F,G,H,}

S={A}

T={r,s}