Information Technology Reference
In-Depth Information
step is taken (basis for induction),
r
=
t
, nothing is popped and the string
is read by
M
.
Since the grammar
G
contains the rule
<r
,
,
r>
, the basis is established.
Suppose that the “if ” portion of the claim is true for
k
or fewer steps (inductive hypoth-
esis). We show that it is true for
k
+
1 steps (induction step). If the PDA
M
can move
from
r
to
t
in
k
+
1stepswhilereading
w
=
x
v
and removing
u
from the stack, then on
its first step it must execute a transition
(
r
,
x
,
y
;
q
,
z
)
,
q
→
∈
Q
,
z
∈
Γ
∪{
}
,for
x
∈
Σ
with
either
y
=
u
if
u
=
or
y
=
. In the first case,
M
enters state
q
,pops
u
,andpushes
z
.
M
subsequently pops
z
as it reads
v
and moves to state
t
in
k
steps. It follows from the
inductive hypothesis that
<q
,
z
,
t>
∗
⇒
G
v
.Since
y
=
, a rule of type (3) applies, that is,
x<q
,
z
,
t>
. It follows that
<r
,
y
,
t>⇒
G
w
, the desired conclusion.
In the second case
y
=
and
M
makes the transition
(
r
,
x
,
;
q
,
z
)
by moving from
r
to
t
and pushing
z
while reading
x
.Topop
u
, which must have been at the top of the stack,
M
must first pop
z
and then pop
u
.Letitpop
z
as it moves from
q
to some intermediate state
t
while reading a first portion
v
1
of the input word
v
.Letitpop
u
as it moves from
t
to
t
while reading a second portion
v
2
of the input word
v
.Here
v
1
v
2
=
v
.Sincethemovefrom
q
to
t
and from
t
to
t
each involves at most
k
steps, it follows that the goals
<q
,
z
,
t
>
and
<t
,
u
,
r>
satisfy
<q
,
z
,
t
> ⇒
G
v
1
and
<t
,
u
,
r>⇒
G
v
2
.Because
M
's fir s t
transition meets condition (4), there is a rule
<r
,
u
,
t>
<r
,
y
,
t>
→
x<q
,
z
,
t
>< t
,
u
,
r>
.
→
Combining these derivations yields the desired conclusion.
Now we establish the “only if ” part of the claim, namely, if for all
r
,
t
∈
Q
and
u
∈
,
<r
,
u
,
t>
∗
Γ
⇒
G
w
, then the PDA
M
can move from state
r
to state
t
while
reading
w
and removing
u
from the stack. Again the proof is by induction, this time on
the number of derivation steps. If there is a single derivation step (basis for induction),
it must be of the type stated in condition (2), namely
<p
,
,
p>
∪{
}
.Since
M
can
move from state
p
to
p
without reading the tape or pushing data onto its stack, the basis is
established.
Suppose that the “only if ” portion of the claim is true for
k
or fewer derivation steps
(inductive hypothesis). We show that it is true for
k
+
1 steps (induction step). That is,
if
<r
,
u
,
t>
∗
→
⇒
G
w
in
k
+
1 steps, then we show that
M
can move from
r
to
t
while
reading
w
and popping
u
from the stack. We can assume that the first derivation step is of
type (3) or (4) because if it is of type (2), the derivation can be shortened and the result fol-
lows from the inductive hypothesis. If the first derivation is of type (3), namely, of the form
<r
,
u
,
t>
→
x<q
,
z
,
t>
, then by the inductive hypothesis,
M
can execute
(
r
,
x
,
u
;
q
,
z
)
,
=
,thatis,read
x
,pop
u
,push
z
, and enter state
q
.Since
<r
,
u
,
t>⇒
G
w
,where
w
=
x
v
, it follows that
<q
,
z
,
t>
∗
u
⇒
G
v
. Again by the inductive hypothesis
M
can move
from
q
to
t
while reading
v
and popping
z
. Combining these results, we have the desired
conclusion.
If the first derivation is of type (4), namely,
<r
,
u
,
t>
x<q
,
z
,
t
>< t
,
u
,
t>
,
then the two non-terminals
<q
,
z
,
t
>
and
<t
,
u
,
t>
must expand to substrings
v
1
and
v
2
, respectively, of
v
where
w
=
x
v
1
v
2
=
x
v
.Thatis,
<q
,
z
,
t
>
∗
→
⇒
G
v
1
and
<t
,
u
,
t>⇒
G
v
1
. By the inductive hypothesis,
M
can move from
q
to
t
while read-
ing
v
1
and popping
z
and it can also move from
t
to
t
while reading
v
2
and popping
u
.Thus,
M
can move from
r
to
t
while reading
w
and popping
u
, which is the desired
conclusion.
Search WWH ::
Custom Search