Contoh Soal Pda

Oleh Vicky Ssy

15 tayangan
Bagikan artikel

Transkrip Contoh Soal Pda

Contoh Soal PDA
1.
ContohQ ={ q1, q2} ∑ ={a,b} Г = {A, B, Z} S = q1 F ={ q2} Z = Z Apakah string “abba”
diterima?
Δ( q1, ε, z) = {( q2, z)}
Δ( q1, a, z) = {( q1, Az)}
Δ( q1, b, z) = {( q1, Bz)}
Δ( q1, a, A) = {( q1, AA)}
Δ( q1, b, A) = {( q1, ε)}
Δ( q1, a, B) = {( q1, ε)}
Δ( q1, b, B) = {( q1, BB)}
Penyelesaian A Z
1. State awal q1, Top Stack Z, Input String “a” Δ( q1, a, z) = {( q1, Az)} push A 2. Input string “b”
dengan tumpukan A Δ( q1, b, A) = {( q1, ε)} pop A
3. Input string “b” dengan tumpukan Z Δ( q1, b, z) = {( q1, Bz)} push B
4. Input string “a” dengan tumpukan B Δ( q1, a, B) = {( q1, ε)} pop B 5. Semua input telah selesai
dibaca Δ( q1, ε, z) = {( q2, z)} Kesimpullan diterima : berakihir di state akhir {( q2, z)}Z B Z Z
2.

Contoh :D → aDA | bDb | cDapatkah menerima string “aca”

Dapat dikontruksikan PDA- nya :
Terdapat 3 produksi :D → aDAD → bDbD → c
Sehingga ada 3 state, maka :Q = {q0, q1, q2}
S = q0
F= {q3 }
∑ = {a, b, c}
Г = { D, a, b, c, Z}
Fungsi transisi Г = { D, a, b, c, Z} :
Transisi D :D → aDA | bDb | c
Δ( q0, ε, z) = {( q1, Dz)}
Δ( q1, ε, D) = {( q1, aDa)}, {( q1, bDb)}, {( q1, c)}
3. Transisi a, b, cΔ( q1, a, a) = Δ( q1, b, b)=Δ( q1, c, c) = {( q1, ε )}
4. Transisi ZΔ( q1, ε, z) = {( q2, z)}
Menerima string “aca” D → aDA ⟹ aca Δ( q0, ε, z) = {( q1, Dz)}
Δ( q1, ε, D) = {( q1, aDa)}Δ( q1, a, a) = {( q1, ε )}Δ( q1, ε, D) = {( q1, c)}Δ( q1, c, c) = {( q1,
ε )}Δ( q1, ε, z) = {( q2, z)}String di terima

Contoh PDAPDA

22 Ide pokok: 2. Cocokkan ‘b’ sbg input dg ‘a’ dlm tumpukan
1. Push ‘a’ ke dalam tumpukan3. Cocok!
23 Contoh Eksekusi:Waktu ke-0MasukanTumpukanKeadaan saat ini
24 Waktu ke-1MasukanTumpukan
25 Waktu ke-2MasukanTumpukan
26 Waktu ke-3MasukanTumpukan
27 Waktu ke-4MasukanTumpukan
28 Waktu ke-5MasukanTumpukan
29 Waktu ke-6MasukanTumpukan
30 Waktu ke-7MasukanTumpukan
31 Waktu ke-8MasukanTumpukanditerima
32 Suatu string diterima jika:
Semua Masukan selesai dieksekusiDANKeadaan terakhir merupakan keadaan yang
diterimaPada keadaan akhir, isi tumpukan tidak diperdulikan (isi tumpukan dapat kosong)

Mesin Turing

Judul: Contoh Soal Pda

Oleh: Vicky Ssy


Ikuti kami