Contoh PDA dan delivasi

Lakukan konfigurasi dan telusuri apakah untai “bcb” di terima atau ditolak gunakan aturan produksi dan fungsi transisi.

    JAWAB

1.       D→aDa | bDb | c

Tupple PDA:

Q = {q1, q2,q3}

∑ = {a,b,c}

Γ= {D,a,b,c,Z}

S = q1

Z = Z

F = {q3}

Fungsi Transisi

Δ(q1, ɛ, Z)=  {(q2, DZ)}

Δ(q2, ɛ, D) = {(q2, aDa), (q2, bDb),(q2,c)}

Δ(q2, a, a) = Δ (q2, b,b)= Δ(q2, c,c)={(q2, ɛ }

Δ(q2, ɛ,Z) = {(q3, Z)}

D→bDb →bcb

F = state q3  di terima