Information Technology Reference
In-Depth Information
T
:
c
a
acaabcbc S
:
a
M
a
N
c
T
:
ca
a
caabcbc S
:
M
a
N
c
T
:
ca
a
caabcbc S
:
a
M
aa
N
c
T
:
caa
c
aabcbc S
:
M
aa
N
c
T
:
caa
c
aabcbc S
:
c
aa
N
c
T
:
caac
a
abcbc S
:
a
a
N
c
T
:
caaca
a
bcbc S
:
a
N
c
T
:
caacaa
b
cbc S
:
N
c
T
:
caacaabcbc S
:
b
N
bc
T
:
caacaabcbc S
:
N
bc
T
:
caacaa
bc
bc S
:
c
bc
T
:
caacaabc
b
c S
:
b
c
T
:
caacaabc
bc
S
:
c
T
:
caacaabcbc
β
S
:
γ
Figure 4.30
PDA transitions corresponding to the leftmost derivation of the string
caacaabcbc
in the grammar
G
3
of Example
4.11.1
.
.
THEOREM
4.12.2
For each PDA
M
there is a context-free grammar
G
that generates the language
L
(
M
)
accepted by
M
.Thatis,
L
(
G
)=
L
(
M
)
.
Proof
It is convenient to assume that when the PDA
M
accepts a string it does so with
an empty stack. If
M
is not of this type, we can design a PDA
M
accepting the same
language that does meet this condition. The states of
M
consist of the states of
M
plus
three additional states, a new initial state
s
, a cleanup state
k
, and a new final state
f
.Its
tape symbols are identical to those of
M
. Its stack symbols consist of those of
M
plus one
new symbol
κ
. In its initial state
M
pushes
κ
onto the stack without reading a tape symbol
and enters state
s
, which was the initial state of
M
.Itthenoperatesas
M
(it has the same
transitions) until entering a final state of
M
, upon which it enters the cleanup state
k
.In
this state it pops the stack until it finds the symbol
κ
, at which time it enters its final state
f
. Clearly,
M
accepts the same language as
M
but leaves its stack empty.
We describe a context-free grammar
G
=(
,
S
)
with the property that
L
(
G
)=
L
(
M
)
. The non-terminals of
G
consist of
S
and the triples
<p
,
y
,
q>
defined below
denoting goals:
N
T
R
,
,
<p
,
y
,
q>
∈N
N⊂
Q
×
(Γ
∪{
}
)
×
Q
where
The meaning of
<p
,
y
,
q>
is that
M
moves from state
p
to state
q
in a series of steps
during which its only effect on the stack is to pop
y
.Thetriple
<p
,
,
q>
denotes the goal
of moving from state
p
to state
q
leaving the stack in its original condition. Since
M
starts
with an empty stack in state
s
with a string
w
on its tape and ends in a final state
f
with
its stack empty, the non-terminal
<s
,
,
f>
,
f
F
, denotes the goal of
M
moving from
state
s
to a final state
f
on input
w
, and leaving the stack in its original state.
∈
Search WWH ::
Custom Search