AGUS BUDI : TEORI BAHASA & OTOMATA

TEORI BAHASA & OTOMATA

Dosen Agus Suharto

بِسْمِ اللهِ الرَّحْمنِ الرَّحِيمِ

Nama : Agus Budiyanto
NIM    : 161021450543
Kelas  : 05TPLM003

1.       Deterministic Finite Automata (DFA)

Ketentuan DFA adalah dari suatu state ada tepat satu state berikutnya untuk setiap simbol masukan yang diterima.

FORMAL PENULISAN

M = (Q, ∑, δ, S, F),

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

•       ∑ = {0,1}

•       S = q0

•       F = {q0}

•       δ  = 

Q	0	1
q0	q0	q1
q1	q2	q1
q2	q0	q3
q3	q0	q1

DIAGRAM

UJI INPUT

  

Berdasarkan hasil dari langkah di atas maka akan didapat hasil sebagai berikut :

INPUT  : 101010 : REJECT

INPUT : 110111

INPUT : 011011

2.       Non-deterministic Finite Automata (NFA)

Ketentuan NFA :

•       Untuk setiap state tidak selalu tepat ada satu state berikutnya untuk setiap simbol input yang ada.

•       Dari suatu state bisa terdapat 0,1 atau lebih busur keluar (transisi) berlabel simbol input yang sama.

FORMAL PENULISAN

M = (Q, ∑, δ, S, F),

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

•       ∑ = {0,1}

•       S = q0

•       F = {q1}

•       δ  = 

Q	0	1
q0	q1	q2, q0
q1	q0	q1
q2	q3	q1, q2
q3	q1	q1

DIAGRAM

UJI INPUT

Berdasarkan hasil dari langkah di atas maka akan didapat hasil sebagai berikut

INPUT : 110110  : ACCEPT

 

111000 : ACCEPT

100111 : ACCEPT

PUSHDOWN AUTOMATA  (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.

FORMAL PENULISAN

Q = {q0, q1, q2, q3}

Σ = {a, b}

Γ = {b, Z}

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

qs= q0

 F = {q3}

DIAGRAM

UJI INPUT

 

Berdasarkan hasil dari langkah di atas maka akan didapat hasil sebagai berikut :

INPUT : baabaa : ACCEPT

INPUT : bbaabb : REJECT

INPUT : bbabab : REJECT

SEKIAN