From CFG to PDA: Example 2/2
M  = (Q, S, G, R, s, S, F), where:
Q = {s}, S = T = {(, )}, G = {(, ), S}, F = Æ
P = {(s( ® s,    )s) ® s,    Ss ® )S(s,    Ss ® )(s }
Question: (( )) Î L(M)e?
Rule: Ss ® )S(s
Answer: YES
(
(
)
)
S
S
Rule: (s( ® s
Rule: Ss ® )(s
Rule: )s) ® s
Rule: )s) ® s
Rule: (s( ® s
Empty pushdown
S
s
)
(
(
)
)
(
S
s
)
(
)
)
s
)
(
)
)
)
(
s
)
)
)
)
s
)
)
s
(
)
S
S
S
(
)
S
S
(
(
)
)
S
S
(
(
)
)
S
S
(
(
)
)
S
S
S
s
)
(
(
)
49/50