DFA, NFA dan PDA

DFA(Deterministic Finite Automata) 
DFA adalah FSA(finite state automata) yang memiliki stata penerima tepat satu stata untuk setiap simbol masukan.
String x dinyatakan diterima,  bila ᵟ (s.x) berada pada state akhir Bila Madalah bahasa FSA

Q= {q0, q1, q2, q3}

∑= {0,1}

S= q0

F= {q2}

ᵟ=

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

setelah di beri input:

10010= Accept karena inputan berhasil mencapai state akhir

input: 

01101 = REJECT karena titik berakhirnya tidak di q2(finish)

input: 

11110 = REJECT karena titik berakhirnya tidak di q2(finish)

NFA

Nondeterministic Finite Automata (NFA) adalah salah satu bagian dari otomata berhingga atau Finite State Automata (FSA). ... Nondeterministic Finite Automata(NFA) didefenisikan sebagai M yang merupakan sebuah koleksi dari 5 obyek (Q , Σ , s , F , ∆ )

Suatu string diterima oleh DFA bila terdapat suatu urutan transisi sehubungan dengan input string tsb dari state awal sampai state akhir.

•NFA harus dicoba semua kemungkinan yang ada sampai terdapat satu yang mencapai state akhir.

Q= {q0, q1, q2, q3, q4}

∑= {0,1}

S= q0

F= {q4}

ᵟ=

q	0	1
q0	q0	q1
q1	q0	q2
q2	q2,q3	q3
q3	q4	-
q4	-	q3

 contoh input:
11010 (accept)  Karena mencapai state akhir

contoh input:

1010 (accept) Karena mencapai state akhir

contoh input:

1111 (reject) Karena tidak mencapai state akhir

PDA

PDA adalah mesin otomata yang memiliki kendali masukan menggunakan teknik LIFO (Last In First Out), untuk menentukan apakah suatu output diterima atau tidak oleh mesin tsb. Dalam melakukan proses peneerimaan input, PDA menggunakan memory stack.

Q = {q0, q1, q2, q3}

 Σ = {a, b} 

Γ = {a, Z} 

δ = {(q0, b, Z, q1, bZ), (q1, a, b, q1, ab), (q1, b, a, q2, λ), (q2, a, b, q3, ab), (q3, b, a, q1, ba)

 qs= q0

 F = {q3} 

manggunakan inputan= babab