Information Technology Reference
In-Depth Information
The rules of
G
, which represent goal refinement, are described by the following con-
ditions. Each condition specifies a family of rules for a context-free grammar
G
.Each
rule either replaces one non-terminal with another, replaces a non-terminal with the empty
string, or rewrites a non-terminal with a terminal or empty string followed by one or two
non-terminals. The result of applying a sequence of rules is a string of terminals in the
language
L
(
G
)
. Below we show that
L
(
G
)=
L
(
M
)
.
→
<s
,
,
f>
∀
f
∈
F
1)
S
<p
,
,
p>
→
∀
p
∈
Q
2)
<p
,
y
,
r>
→
x<q
,
z
,
r>
∀
r
∈
Q
and
∀
(
p
,
x
,
y
;
q
,
z
)
∈
Δ
,
3)
where
y
=
4)
<p
,
u
,
r>
→
x<q
,
z
,
t><t
,
u
,
r>
∀
r
,
t
∈
Q
,
∀
(
p
,
x
,
;
q
,
z
)
∈
Δ
,
and
∀
u
∈
Γ
∪{
}
Condition (1) specifies rules that map the start symbol of
G
onto the goal non-terminal
symbol
<s
,
,
f>
for each final state
f
. These rules insure that the start symbol of
G
is
rewritten as the goal of moving from the initial state of
M
to a final state, leaving the stack
in its original condition.
Condition (2) specifies rules that map non-terminals
<p
,
,
p>
onto the empty string.
Thus, all goals of moving from a state to itself leaving the stack in its original condition can
be ignored. In other words, no input is needed to take
M
from state
p
back to itself leaving
the stack unchanged.
Condition (3) specifies rules stating that for all
r
=
,thatare
transitions of
M
,agoal
<p
,
y
,
r>
to move from state
p
to state
r
while removing
y
from
the stack can be accomplished by reading tape symbol
x
, replacing the top stack symbol
y
with
z
, and then realizing the goal
<q
,
z
,
r>
of moving from state
q
to state
r
while
removing
z
from the stack.
Condition (4) specifies rules stating that for all
r
,
t
∈
Q
and
(
p
,
x
,
y
;
q
,
z
)
,
y
Q
and
(
p
,
x
,
;
q
,
z
)
that are
transitions of
M
,thegoal
<p
,
u
,
r>
of moving from state
p
to state
r
while popping
u
for arbitrary stack symbol
u
can be achieved by reading input
x
and pushing
z
on top of
u
and then realizing the goal
<q
,
z
,
t>
of moving from
q
to some state
t
while popping
z
followed by the goal
<t
,
u
,
r>
of moving from
t
to
r
while popping
u
.
We now show that any string accepted by
M
can be generated by
G
and any string
generated by
G
can be accepted by
M
. It follows that
L
(
M
)=
L
(
G
)
.Insteadofshowing
this directly, we establish a more general result.
∈
,
<r
,
u
,
t>
∗
CLAIM:
For all
r
,
t
⇒
G
w
if and only if the PDA
M
can move from state
r
to state
t
while reading
w
and popping
u
from the stack.
∈
Q
and
u
∈
Γ
∪{
}
The theorem follows from the claim because
<s
,
,
f>⇒
G
w
if and only if the PDA
M
can move from initial state
s
to a final state
f
while reading
w
and leaving the stack
empty, that is, if and only if
M
accepts
w
.
We first establish the “if ” portion of the claim, namely, if for
r
,
t
}
the PDA
M
can move from
r
to
t
while reading
w
and popping
u
from the stack, then
<r
,
u
,
t>
∗
∈
Q
and
u
∈
Γ
∪{
⇒
G
w
. The proof is by induction on the number of steps taken by
M
.Ifno
Search WWH ::
Custom Search