UTS Pengantar Bahasa dan Otomata (RYAN GESVARY/161021450492/ERESHA/05TPLM003)

UTS PENGANTAR BAHASA DAN OTOMATA

Dosen Agus Suharto

   Assallamuallaikum wr.wb. Salam sehat dan positif selalu dalam menjalani setiap hidup.

Kali ini saya akan memaparkan beberaapa tugas Pengantar Bahasa dan Otomata yang meliputi 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 ∑.  Automata ini bersifat deterministik, yang artinya automata tersebut tidak dapat berada di lebih dari satu state pada saat bersamaan. NFA bersifat non-deterministik, yang artinya automata ini dapat berada di beberapa state pada saat yang bersamaan. PDA (Pushdown Automata) adalah mesin otomata yang memiliki kendali masukan menggunakan teknik LIFO (Last In First Out), dimana suatu output diterima atau tidak oleh mesin yang sudah di input. Dalam proses peneerimaan input, PDA menggunakan memory stack.

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 (1 dan 0).

·         State terima(Final) q3, dengan lingkaran ganda.

Deskripsi :

M1=( Q, Σ, δ, S, F)

Q = {q0, q1, q2, q3}

Σ = {1, 0}

δ = 

δ	1	0
q0	q1	q2
q1	q2	q1
q2	ø	q0
q3	q0	Ø

S = {q0} awal/initial state

F = {q3} final state

Hasil test step by state Run diagram M1

Berikut hasil running awal yang saya input. Disini saya inputkan 11100 dan hasilnya Accept.

Lalu yang kedua saya running dan inputkan 10110. Hasilnya pun juga demikian, Accept.

Berikut hasil running yang ketiga. Saya inputkan 11110 dan hasilnya, Accept.

 

2.       NFA (Non-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 (1 dan 0).

·         State terima(Final) q1, dengan lingkaran ganda.

Deskripsi :

M2=( Q, Σ, δ, S, F)

Q = {q0, q1, q2, q3}

Σ = {1, 0}

δ =

δ	1	0
q0	q2,q2	q3
q1	q0	Ø
q2	q3	q2
q3	ø	q3

Hasil test step by state Run diagram M1

Berikut hasil running. Dengan hasil inputan 00011.

Selanjutnya hasil running dengan nilai inputan 10100.

Lalu hasil running yang terakhir, dengan nilai hasil inputan 10010.

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 (a, b).

·         State terima(Final) q3, dengan lingkaran ganda.

Deskripsi :

M3=( Q, Σ, δ, S, F)

Q = {q0, q1, q2, q3}

Σ = {a, b}

Γ = {a, Z}

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

S = {q0}

F = {q3}

Hasil test step by state Run diagram M1

Untuk proses runiing hasil inputannya. Pertama saya input dengan transisi aaabb, lalu abb dan terakhir aabb. Disatu sisi dengan bagan desain yang sudah saya buat, hasil inputan tidak terhitung sebagai 5 kata, melainkan disini saya menginputnya secara acak.

Berikut screenshot yang saya berikan.

Sekian tugas dari saya, bila ada kesalahan dalam penulisan dan penerangan yang saya buat dalam tugas ini. Harap dimaklumi dan semoga anda yang berkenaan membacanya bermanfaat bagi lainnya.