From CFG to PDA: Example 1/2
• G = (N, T, P, S), where:
  N = {S}, T = {(, )}, P = {S ® (S), S ® ( )}
M  = (Q, S, G, R, s, S, F) where:
Objective: An PDA  M such that L(G) = L(M)e
S ® (S) Î P
Q = {s};
S = T = {(, )};
G = N È T = {S, (, )}
R = {
“(” Î T
(s( ® s,
)s) ® s,
Ss ® )S(s,
Ss ® )(s }
S ® ( ) Î P
“)” Î T
F = Æ
rev
rev
48/50
popping rules
expansion rules