From CFG to EPDA: Example 1/2
• G = (N, T, P, S), where:
  N = {S}, T = {(, )}, P = {S ® (S), S ® ( )}
M  = (Q, S, G, R, s, #, F) where:
Objective: An EPDA  M such that L(G) = L(M)f
S ® (S) Î P
Q = {s, f};
S = T = {(, )};
G = N È T È {#} = {S, (, ), #}
R = {
“(” Î T
s( ® (s,
s) ® )s,
(S)s ® Ss,
( )s ® Ss,
#Ss ® f }
S ® ( ) Î P
“)” Î T
shift rules
reduction rules
F = {f}
43/50