From CFG to EPDA: Example 2/2
M  = (Q, S, G, R, s, #, F), where:
Q = {s, f}, S = T = {(, )}, G = {(, ), S, #}, F = {f}
R = {s( ® (s, s) ® )s, (S)s ® Ss, ( )s ® Ss, #Ss ® f }
Question: (( )) Î L(M)f?
Rule: s( ® (s
#
s
)
(
(
)
f
Answer: YES
(
(
)
)
S
S
#
s
)
(
(
)
#
s
)
(
(
)
Rule: s( ® (s
Rule: s) ® )s
#
s
)
(
(
)
Rule: s) ® )s
#
s
)
(
S
Rule: (S) ® S
Rule: #Ss ® f
Rule: ( )s ® S
#
s
)
(
S
#
s
S
(
(
)
)
S
(
(
)
S
(
(
)
(
(
(
Final state
44/50