TUGAS UTS PENGANTAR BAHASA DAN OTOMATA
1. UTS PENGANTAR BAHASA DAN OTOMATA
NAMA : MUHAMMAD SIDIQ JAELANI PANGESTU
NIM : 161021450502
KELAS : 05TPLM003
Deterministic
Finite Automata (DFA)
Ketentuan DFA adalah dari suatu state ada tepat satu state berikutnya
untuk setiap simbol masukan yang diterima.
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
Berdasarkan hasil dari langkah di atas maka
akan didapat hasil sebagai berikut :
INPUT :
101010 : REJECT
INPUT : 110111
2.
Non-deterministic
Finite Automata (NFA)
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
Berdasarkan hasil dari langkah di atas maka
akan didapat hasil sebagai berikut
INPUT : 110110 : ACCEPT
111000 : ACCEPT
100111 : ACCEPT
3.PDA (Pushdown automata)
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, q3, xy)}
- 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.
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, q3, 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.
Comments
Post a Comment