Information Technology Reference
In-Depth Information
a)
(
s
,
,
;
p
,
S
)
b)
(
p
,
a
,
a
;
p
,
)
∀
a
∈T
c)
(
p
,
,
A
;
p
,
v
)
∀
(
A
→
v
)
∈R
d)
(
p
,
,
γ
;
f
,
)
Let
w
be placed left-adjusted on the input tape of
M
.Since
w
is generated by
G
,ithas
a leftmost derivation. (Consider for example that given in (
4.2
)onpage
186
.) The PDA
begins by pushing the start symbol
S
onto the stack and entering state
p
(Rule (a)). From
this point on the PDA simulates a leftmost derivation of the string
w
placed initially on its
tape. (See the example that follows this proof.)
M
either matches a terminal of
G
on the top
of the stack with one under the tape head (Rule (b)) or it replaces a non-terminal on the top
of the stack with a rule of
R
by pushing the right-hand side of the rule onto the stack (Rule
(c)). Finally, when the stack is empty,
M
canchoosetoenterthefinalstate
f
and accept
w
.
It follows that any string that can be generated by
G
can also be accepted by
M
and vice
versa.
The leftmost derivation of the string
caacaabcbc
by the grammar
G
3
of Example
4.11.1
is shown in (
4.2
). The PDA
M
of the above proof can simulate this derivation, as we show.
With the notation
T
:
...
and
S
:
...
(shown below before the computation begins) we
denote the contents of the tape and stack at a point in time at which the underlined symbols
are those under the tape head and at the top of the stack, respectively. We ignore the blank
tape and stack symbols unless they are the ones underlined.
T
:
c
aacaabcbc
S
:
γ
After the first step taken by
M
, the tape and stack configurations are:
T
:
c
aacaabcbc
S
:
S
From this point on
M
simulates a derivation by
G
3
. Consulting (
4.2
), we see that the rule
S
c
MN
c
is the first to be applied.
M
simulatesthiswiththetransition
(
p
,
,
S
;
p
,
c
MN
c
)
,
which causes
S
to be popped from the stack and
c
MN
c
to be pushed onto it without advancing
the tape head. The resulting configurations are shown below:
→
T
:
c
aacaabcbc
S
:
c
MN
c
Next the transition
(
p
,
c
,
c
;
p
,
)
is applied to pop one item from the stack, exposing the non-
terminal
M
and advancing the tape head to give the following configurations:
T
:
c
a
acaabcbc
S
:
M
N
c
The subsequent rules, in order, are the following:
1
)
M
→
a
M
a
3
)
M
→
c
5
)
N
→
c
2
)
M
→
a
M
a
4
)
N
→
b
N
b
The corresponding transitions of the PDA are shown in Fig.
4.30
.
We now show that the language accepted by a PDA can be generated by a context-free
grammar.
Search WWH ::
Custom Search