UTS TEORI BAHASA DAN AUTOMATA

- April 24, 2019

Assalamualaikum, saya akan memaparkan tugas tentang matakuliah automata :⸙⸙⸙⸙

Tugas UTS AUTOMATA Buat mesin Abstrak
1. DFA
2.NFA
3. PDFA

1. DFA merupakan teori komputasi dan cabang dari ilmu komputer teoritis. DFA adalah Finite-state Machine atau mesin keadaan terbatas yang menerima atau menolak string dari simbol dan hanya menghasilkan perhitungan unik dari otomata untuk setiap string yang di masukan.

ü Definisi Format tuple

Secara Formal FSA dinyatakan dengan 5 Tuple M= (Q, ∑, δ, q0, F ) diantaranya :

1. Q = Himpunan State

2. ∑ = Hhimpunan Simbol Input

3. δ = Transition Function

4. q0 = awal starte

5. F = Final/ set of accept

ü Format Penulisan

Q = {q0,q1,q2,q3}

∑ = {0,1}

δ =

S = q0 start awal

F = Final nya q3

ü Diagram

ü Uji Input

01001 = Diterima

10010 = Diterima

0100 = Ditolak

Keterangan :

01001 = dijalur yang berwarna kuning , itu hasilnya diterima karena berhenti di final

10010 = dijalur yang berwarna hijau tua, itu hasilnya diterima karena berhenti di final

0100 = dijalur yang berwarna merah, tidak diterima karena berhenti tidak di final

2. Finite state automata (FSA) bukanlah mesin fisik tetapi suatu model matematika dari

suatu sistem yang menerima input dan output. FSA merupakan mesin automata dari

bahasa regular (tipe 3). Suatu FSA memiliki state yang banyaknya berhingga, dan dapat

berpindah dari suatu state ke state lain. Perubahan state dinyatakan oleh fungsi transisi.

Suatu FSA secara formal dinyatakan oleh 5 (lima) tupel M = (Q, Σ, δ, S, F) dimana :

Q = Himpunan state / kedudukan

Σ = Himpunan simbol input / masukan

δ = Fungsi transisi

S = State awal / kedudukan awal

F = Himpunan state akhir

FSA berdasar pada pendefinisian kemampuan berubah state-statenya bisa dikelompokkan

kedalam Deterministic Finite Automata dan Non Deterministic Finite Automata.

ü Format Penulisan

Q = {q0,q1,q2,q3,q4}

∑ = {0,1}

δ =

S = q0 start awal

F = Final nya q4

ü Diagram

ü Uji Input

01010 = Diterima

010111 = Diterima

0101 = Ditolak

Keterangan :

01010 = dijalur warna kuning, itu diterima karena berhenti di final

010111 = dijalur warna hijau , itu diterima karena berhenti di final

0101 = dijalur warna pink, ditolak karena berhentinya tidak di final

3. PDFA (Push Down Automata)

PDA adalah mesin otomata dari TBBK yang diimplementasikan dengan stack sehingga hanya terdapat operasi “push” dan “pop” Stack (tumpukan) adalah suatu struktur data yang menggunakan prinsip LIFO (Last In First Out). Sebuah stack selalu memiliki top of stack dan elemen-elemen stack itu yang akan masuk ke dalam stack dengan method “push” dan akan keluar dari stack dengan method “pop”.

Definisi : PDA adalah pasangan 7 tuple M = (Q, Σ, , q 0 , Z 0 , δ, A), dimana :

Q : himpunan hingga stata, Σ : alfabet input, : alfabet stack, q 0 ∈ Q : stata awal Z 0 ∈ : simbol awal stack, A ⊆ Q : himpunan stata penerima,
(Σ ∪ {ε}) ×fungsi transisi δ : Q Q × * *)× (himpunan bagian dari Q

Untuk stata q ∈ Q, simbol input a ∈ Σ, dan simbol stack X∈ , δ(q, a, X) = (p, α) berarti : PDA bertransisi ke stata p dan mengganti X pada stack dengan string α.

Konfigurasi PDA pada suatu saat dinyatakan sebagai triple (q, x, α), dimana :

q ∈ Q : stata pada saat tersebut, x ∈ Σ* : bagian string input yang belum dibaca, dan α ∈ * : string yang menyatakan isi stack dengan karakter terkiri menyatakan top of stack.

Misalkan (p, ay, Xβ) adalah sebuah konfigurasi, dimana : a ∈ Σ, y ∈ Σ*, X ∈ , dan β ∈ *. Misalkan pula δ(p, a, X) = (q, γ) untuk q ∈ Q dan γ ∈ *. Dapat kita tuliskan

bahwa : (p, ay, Xβ) ⇒ (q, y, γβ).
Sebuah PDA dinyatakan dengan :
Q         = himpunan state
Σ          = himpunan simbol input
T          = simbol stack
S          = state awal
F          = state akhir
Z          = top of stack

ü Format Penulisan

M = (Q,⸢,∑, δ, S, F)

Q = (q0, q1,q2,q3,q4)

∑ = (a,b)

δ = (q0, a, z, q1, aZ), (q1,a,a, q1, aa), (q1, b,a,q,λ), (q2,b,a,q2,λ), (q2,b,Z,q3,Z), (q3,b,z,q3,Z)

⸢ = (a,Z)

S = q0
F = q3

ü Diagram