Date: Wed, 08 Jan 1997 20:39:25 GMT Server: NCSA/1.4.2 Content-type: text/html
Basis: Suppose .
The only way this could be true is if A = B and
.
Certainly, A derives A in zero steps, so
in the base case.
Inductive Hypothesis: Assume for all
and
that
implies
.
Inductive Step:
Consider some ,
where
. Since |x| = n+1,
x = ay for some
and
.
The computation must have been
for some
where
.
By the construction of M from G, this means that there must be
a production
in P. Also, by the induction
hypothesis, since
, we know
that
. Thus,
.
Thus, for all ,
,
,
implies
.
() Next we'll show that
for all
and
,
if
, then
for all
by
induction on n:
Basis: Suppose that .
The only way this could be true is if A = B and
.
Since
, the base case is true.
Inductive Hypothesis: Assume for all
and
that
implies
.
Inductive Step:
Consider some ,
where
. Since n+1 > 0 and G is a
regular grammar of the restricted form given in class,
we know that the first step of the derivation involves a
production of the form
where
is the first character of x and
. Thus, the derivation
looks like
where x = ay.
This means that
, so by the induction
hypothesis,
. In addition,
by our construction of
and the fact that
, C must be in
,
and so
. Therefore,
.
Thus, for all ,
,
,
implies
.
Proof that :
If , since G is regular then
for some
where
.
If
, then
and
where A=S. In either case
we have for some
:
Thus, M accepts exactly .
Here is an NFA with 6 transitions that accepts the same: