Hallo apa kabar? Semoga sehat selalu yaa. Akhirnya kita berjumpa lagi 😁. Untuk postingan kali ini , saya akan memposting sebuah Teori Bahasa Automata yaitu Membuat Mesin Deterministic Finite Automata (DFA), Non-deterministic
Finite Automata (NFA) dan Pushdown Finite Automata (PDFA)
. Pasti sudah ada yang tahu kan? dan mungkin sudah pernah membuat, langsung saja ya berikut penjelasan tentang Materi di atas :
A. Deterministic Finite Automata (DFA)
DFA
(Deterministic Finite Automata) adalah FSA(finite state automata)
yang memiliki stata penerima tepat satu stata untuk setiap simbol masukan.
Contoh
Kasus
Formal penulisan :
M = (Q, ∑, δ, S, F),
Q = {q0, q1, q2, q3}
∑ = {0,1}
S = q0
F = {q3}
δ =
δ
|
0
|
1
|
Q0
|
Q1
|
Q0
|
Q1
|
Q3
|
Q2
|
Q2
|
0
|
Q3
|
Q3
|
Q1
|
0
|
Hasil Uji Input :
Penjabaran Uji Input sebagai
berikut :
Input
1011 à Accept
Input 1001 à
Reject
Input 01110 à Accept
B. Non-deterministic Finite Automata (NFA)
-
Suatu string diterima oleh DFA bila terdapat suatu
urutan transisi sehubungan dengan input string tersebut dari state awal sampai state
akhir.
-
NFA harus dicoba semua kemungkinan yang ada sampai
terdapat satu yang mencapai state akhir.
-
Suatu string x dinyatakan diterima oleh bahasa NFA, M
= (Q, ∑, δ,
S,
F)
-
Bila {x | δ(S,x) memuat sebuah state di dalam F}
Contoh Kasus :
Formal penulisan :
M = (Q, ∑, δ, S, F),
Q = {q0, q1, q2, q3}
∑ = {0,1}
S = q0
F = {q2}
δ =
δ
|
0
|
1
|
Q0
|
Q1,Q2
|
Q0
|
Q1
|
0
|
Q2
|
Q2
|
Q3
|
0
|
Q3
|
0
|
Q1
|
Hasil Uji Input :
Penjabaran Uji Input sebagai
berikut :
Input 1010 à
Reject
Trace
Input 1100 à
Reject
Trace
Input 1101 à
Reject
Trace
C. Pushdown Finite Automata (PDFA)
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.
Contoh Kasus
Formal
penulisan :
Q = {q0, q1, q2}
Σ =
{a, b}
Γ = {b,
Z}
δ =
{(q0, b, b, q0, bb), (q0, b, Z, q0, bZ), (q1, a, b, q1, λ), (q1, λ, Z, q2, Z)}
qs= q0
F = {q2}
Z
Hasil Uji Input :
Input bbbbaa à
Reject
Trace
Input bbbaa à
Reject
Trace
Input bbbbaaaa à
Accept
Trace
Sekian penjelasan mengenai DFA, NFA, dan PDFA apabila ada kurangnya saya mohon maaf.
Terimakasih dan semoga bermanfaat untuk semuanya.
Wassalamu'alaikum Wr. Wb.
