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
®
S
s
,
(
)
s
®
S
s
,
#
S
s
®
f
}
S
®
( )
Î
P
“)”
Î
T
shift rules
reduction rules
F
= {
f
}
43/50