EPDA: Example
M = (Q, S, G, R, s, S, F)
• S = {a, b};
where:
• G = {a, b, S, C};
s
• Q = {s, f};
f
• F = {f}
     s   ® Cs,
e/C, e
SC/e, e
SCs   ®   f  }
aCsa ® Cs,
aC/C, a
• R = {     sa ® as,
e/a, a
     sb ® bs,
e/b, b
bCsb ® Cs,
bC/C, b
Ssabba
|– Sasbba
|– Sabsba
|– SabCsba
|– SaCsa
|– f
|– SCs
Question: abba Î Lfe(M)?
Answer: YES
Note: L(M)f = L(M)e = L(M)fe  = {xy: x, y Î S*, y = reversal(x)}
36/50