Assalamu'alaikum warahmatullohi wabarakatuh
Alhamdulillahirobbil 'alamiin, telah diselesaikan laporan tugas untuk memenuhi nilai Ujian Tengah Semester V mata Kuliah Teori Bahasa dan Otomata. Adapun Tugasnya adalah membuat mesin Finite State Automata diantaranya Mesin DFA, NFA, dan PDA. Berikut uraiannya :
1. DFA (Deterministic Finite
Automata)
1.1. Pengertian
DFA
Deterministic Finite Automata
merupakan sebuah fungsi yang harus terdefinisi untuk semua pasangan state-input
yang ada didalam Q X ∑. Deterministik finite automata (DFA) bersifat deterministik,
yang berarti bahwa automata tersebut tidak dapat berada di lebih dari satu
state pada saat yang bersamaan.
1.2. Membuat mesin DFA
a. Formal Definition Tuple
b.
Diagram FSA
c. Uji
Input
Untuk melakukan pengujian
terhadap mesin NFA diatas, dilakukan 3 sample input yang berbeda,diantaranya :
-
11000
Berdasarkan
trace inputan berupa gambar diatas, menunjukan inputan 11000 tidak dapat
diterima oleh mesin DFA, karena tidak berakhir pada final state yaitu state q2,
inputan diatas berakhir pada state q3.
-
00010
Pada ujicoba input kedua dengan nilai input yang
berbeda, inputan diterima karena berakhir pada final state yaitu q2.
-
10011
Nilai
input 10011 diterima mesin DFA karena berakhir pada state akhir.
Berikut adalah tampilan ketika inputan dijalankan.
2.
NFA (Non-Determinaistic Finite Automata)
2.1. Pengertian NFA
Non-deterministik finite automata (NFA) bersifat non-deterministik, yang
berarti bahwa automata tersebut dapat berada di beberapa state pada saat yang
bersamaan atau dengan kata lain NFA dapat menebak di state mana dia berikutnya
akan berada (Hopcroft et al., 2007).Pada Non-Determinaistic Finite Automata
(NFA) dari suatu state bisa terdapat 0,1, atau lebih busur keluar (transisi)
berlabel simbol input yang sama. Non-Determinaistic Finite Automata
didefenisikan pula dengan lima(5) M=(Q , Σ , δ , S , F )dengan arti yang serupa
pada Deterministic Fnite Automata. Disini perbedaan ada padafungsi transisinya,
dimana untuk setiap pasangan state-input, kita bisa memiliki 0 (nol) atau lebih
pilihan untuk state berikutnya.
2.2.
Membuat mesin NFA
a.
Formal Definition Tuple
b.
Diagram FSA
c.
Uji Input
-
111010
= Diterima, karena berakhir pada final state.
-
110101
= Tidak diterima, karena berakhir pada q2, bukan pada final state q3.
-
101010
=Diterima, Karena berakhir pada final state.
Tampilan hasil ketiga input diatas saat dijalankan.
13. PDA
(PUSH DOWN AUTOMATA)
3.1. Pengertian PDA
Push Down Automata (PDA) merupakan mesin otomata dari bahasa bebas
konteks.PDA di gambarkan sebagai tempat penyipanan yang tidak terbatas berupa
stack/ tumpukan.Stack merupakan kumpulan dari elemen-elemen sejenis dengan
sifat penambahan elemen dan pengambilan elemen melalui suatu tempat yang
disebut top of stack(puncak stack).Pengambilan elemen dari stack dinyatakan
dengan operasi pop sedangkanmemasukkanelemen kedala stack dengan posisi push.
3.2. Membuat Mesin PDA
a. Formal Definition Tuple
M3=( Q, Σ, δ, S, F)
Q = {q0, q1, q2, q3, q4}
∑={a,b,Z,λ}
Γ = {b, Z}
δ = {(q0, b, Z, q1, bZ), (q1, b, b, q1, bb), (q1, b,
b, q2, λ ), (q2, λ, Z, q3, Z), (q4, a, a, q3, ab)}
S = {q0}
F = {q3}
b. Diagram PDA
c. Uji Input
 |
| INPUT DITERIMA |
 |
| INPUT DITERIMA |
 |
| INPUT DITERIMA |
Demikian laporan yang bisa saya sampaikan, mohon maaf atas kekurangannya, semoga bermanfaat untuk khazanah ilmu.
Terimakasih
Salam,
Muhammad Sobari
