MuhammadSobari: UTS MATAKULIAH TEORI BAHASA DAN OTOMATA

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