Assalamualaikum Wr.Wb. Pada kesempatan kali ini saya akan memaparkan tugas tentang matakuliah AUTOMATA
Tugas Ujian Tengah Semester (UTS) AUTOMATA
1.DFA
2.NFA
3.PDA
1. Deterministic Finite Automata (DFA)
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.
FORMAL PENULISAN
M = (Q, ∑, δ, S, F),
•
Q
= {q0,q1, q2, q3}
•
∑
= {0,1}
•
S
= q0
•
F
= {q0}
•
δ
=
Q
|
0
|
1
|
q0
|
q0
|
q1
|
q1
|
q2
|
q1
|
q2
|
q0
|
q3
|
q3
|
q0
|
q1
|
DIAGRAM & UJI INPUT
2. Non-deterministic Finite Automata (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
Ketentuan NFA :
• Untuk setiap state tidak selalu
tepat ada satu state berikutnya untuk setiap simbol input yang ada.
• Dari suatu state bisa terdapat 0,1
atau lebih busur keluar (transisi) berlabel simbol input yang sama.
FORMAL PENULISAN
M = (Q, ∑, δ, S, F),
•
Q
= {q0,q1, q2, q3}
•
∑
= {0,1}
•
S
= q0
•
F
= {q1}
•
δ
=
Q
|
0
|
1
|
q0
|
q1
|
q2, q0
|
q1
|
q0
|
q1
|
q2
|
q3
|
q1, q2
|
q3
|
q1
|
q1
|
DIAGRAM & UJI INPUT
3. PUSHDOWN AUTOMATA (PDA)
PDA 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.
Formal 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
F = q3
DIAGRAM & UJI INPUT
Komentar
Posting Komentar