PDA: Example
M = (Q, S, G, R, s, S, F)
• S = {a, b};
where:
• G = {a, S};
apa ® aap,
• Q = {s, p, q, f};
• R = {Ssa ® Sap,
apb ® q,
Sq   ® f}
• F = {f}
aqb ® q,
Question: aabb Î L(M)fe?
Ssaabb
|– Sapabb
|– Saapbb
|– Saqb
|– Sq
|– f
Rule: Ssa ® Sap
S
s
b
a
a
b
p
a
S
a
b
b
q
S
a
b
p
S
a
a
b
b
Rule: apa ® aap
Rule: apb ® q
Rule: aqb ® q
Rule: Sq   ® f
S
q
f
Answer: YES
Empty pushdown
Final state
Note: L(M)f = L(M)e = L(M)fe  = {anbn: n ³ 1}
30/50