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
,
S
s
®
)
S
(
s
,
S
s
®
)
(
s
}
Question
:
(( ))
Î
L
(
M
)
e
?
Rule:
S
s
®
)
S
(
s
Answer:
YES
(
(
)
)
S
S
Rule:
(
s
(
®
s
Rule:
S
s
®
)
(
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