Tugas UAS Algoritma (Gunari Ahmad Rafirman/161021450550)

UTS PENGANTAR BAHASA DAN OTOMATA

Dosen Agus Suharto

Soal UTS automata

1. Buat mesin abstrak automata

Setiap mahasiswa masing2 3 jenis

a. DFA

b. NFA

c. PDA

Deskripsikan dengan format tuplenya

Berikan input untuk setup FA min 3 input

2. Buat laporan pada Blog untuk pengumpulannya 

Terdiri dari :

a. Deskripsi

b. Format penulisan

c. Diagram

d. Uji input

Assalamualaikum salam sejahtera bagi kita semua...

Kali ini tugasnya adalah DFA (Deterministic Finite Automata), NFA (Non-Deterministic Finite Automata) dan PDA (Pushdown Automata). DFA adalah sebuah fungsi yang harus terdefinisi untuk semua pasangan state-input yang ada didalam Q X ∑. Deterministik finite automata bersifat deterministik, yang berarti bahwa automata tersebut tidak dapat berada di lebih dari satu state pada saat yang bersamaan. 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. PDA (Pushdown Automata) 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 mesin abstrak :

1. DFA (Deterministic Finite Automata)

• Gambar di atas disebut diagram state M1.
• Ia memiliki empat state, berlabel q0, q1, q2 dan q3.
• State awal(Initial) yaitu q0, ditunjukkan oleh panah yang menunjuknya entah dari mana.
• Panah yang berpindah dari satu kondisi ke kondisi lain disebut transisi (a dan b).
• State terima(Final) q1, dengan lingkaran ganda.

Deskripsi :

M1=( Q, Σ, δ, S, F)
Q = {q0, q1, q2, q3}

Σ = {a, b}

δ =

δ	a	b
q0	q0	q1
q1	q3	ø
q2	ø	q0
q3	q2	q3

S = {q0} awal/initial state

F = {q1} final state

Hasil test step by state Run diagram M1

Saya menginputkan data bababb dan hasilnya adalah accept. Transisi awal adalah b melalui state awal/initial yaitu q0 menuju q1 dan transisi seterusnya sampai dengan transisi terakhir yaitu b dari state q0 menuju state final yaitu q1.

Inputan data abaabb dan hasilnya adalah accept. Transisi awal adalah a melalui state awal yaitu q0 menuju q0 dan transisi seterusnya sampai dengan transisi terakhir yaitu b dari state q0 menuju state final yaitu q1. Jadi apa bila data yang diinputkan berakhiran pada state final yaitu q1 maka hasilnya accept.

Inputan ketiga data aba dan hasilnya adalah reject. Pada data ini transisi awal adalah a melalui state awal yaitu q0 menuju q0 dan transisi seterusnya sampai dengan transisi terakhir yaitu a dari state q1 menuju state q3. Yang membuat hasil data ini tidak diterima yaitu karena state q3 bukan merupakan state final maka hasilnya adalah reject.

2. NFA (Non-Deterministic Finite Automata)

• Gambar di atas disebut diagram state M2.
• Ia memiliki empat state, berlabel q0, q1, q2 dan q3.
• State awal(Initial) yaitu q0, ditunjukkan oleh panah yang menunjuknya entah dari mana.
• Panah yang berpindah dari satu kondisi ke kondisi lain disebut transisi (a dan b).
• State terima(Final) q1, dengan lingkaran ganda.

Deskripsi :

M2=( Q, Σ, δ, S, F)
Q = {q0, q1, q2, q3}
Σ = {a, b}
δ =

δ	a	b
q0	q0,q1	q1
q1	q3	Ø
q2	Ø	q0,q2
q3	q2	q3

S = {q0} awal/initial state

F = {q1} final state

Hasil test step by state Run diagram M2

Saya menginputkan data abaabb dan hasilnya adalah accept. Transisi awal adalah a melalui state awal yaitu q0 menuju q0 dan transisi seterusnya sampai dengan transisi terakhir yaitu b dari state q0 menuju state final yaitu q1. Jadi apa bila data yang diinputkan berakhiran pada state final yaitu q1 maka hasilnya accept.

Data aab dan hasilnya adalah accept. Transisi awal adalah a melalui state awal yaitu q0 menuju q0 dan transisi seterusnya sampai dengan transisi terakhir yaitu b dari state q0 menuju state final yaitu q1. Sama dengan DFA bila data yang diinputkan berakhiran pada state final yaitu q1 maka hasilnya accept.

Saya menginputkan data ababa dan hasilnya adalah reject. Transisi awal adalah a melalui state awal yaitu q0 menuju q0 dan transisi seterusnya sampai dengan transisi terakhir yaitu a dari state q3 menuju state q2. Karena state q2 bukan merupakan state final maka hasilnya adalah reject.

3. PDA (Pushdown automata)

• Gambar di atas disebut diagram state M3.
• Ia memiliki empat state, berlabel q0, q1, q2 dan q3.
• State awal(Initial) yaitu q0, ditunjukkan oleh panah yang menunjuknya entah dari mana.
• Panah yang berpindah dari satu kondisi ke kondisi lain disebut transisi (x, y).
• State terima(Final) q3, dengan lingkaran ganda.

Deskripsi :

M3=( Q, Σ, δ, S, F)
Q = {q0, q1, q2, q3}
Σ = {x, y}
Γ = {x, Z}
δ = {(q0, x, Z, q1, xZ), (q1, x, x, q1, xx), (q1, y, x, q2, yx), (q2, y, y, q3, yy), (q3, x, y, q2, xy)}

S = {q0}

F = {q3}

Hasil test step by state Run diagram M3

Saya menginputkan data xxyyxyy dan hasilnya adalah accept. Transisi awal adalah x melalui state awal yaitu q0 menuju q1 dan transisi seterusnya sampai dengan transisi terakhir yaitu y dari state q2 menuju state final yaitu q3. Jadi apa bila data yang diinputkan berakhiran pada state final yaitu q3 maka hasilnya accept.

Saya menginputkan data xyyxxxyy dan hasilnya adalah accept. Transisi awal adalah x melalui state awal yaitu q0 menuju q1 dan transisi seterusnya sampai dengan transisi terakhir.

Saya menginputkan data xyyxyy dan hasilnya adalah accept. Transisi awal adalah x melalui state awal yaitu q0 menuju q1 dan transisi seterusnya sampai dengan transisi terakhir. Sama dengan DFA dan NFA bila data yang diinputkan berakhiran pada state final yaitu q3 maka hasilnya accept.

Sekian tugas dari saya, apabila terdapat salah-salah kata saya mohon maaf. Keritik dan saran terbuka dikolom komentar.

Thankss 🙏🙏...

Jangan lupa like, coment and share
Follow juga IG @Rafi_gbl24

Author Gunari Ahmad Rafirman (161021450550)