Date: Wed, 08 Jan 1997 20:48:52 GMT
Server: NCSA/1.4.2
Content-type: text/html
CSE 322
Midterm Solutions
Winter Quarter, 1996
Next: About this document
CSE 322
Midterm Solutions
Winter Quarter, 1996
-
We will use the technique given in the handout and explained by Jim
Fix to construct a regular grammar for
.
Since we eventually need to generate a unique set of non-terminals for
each a and b in the regular expression, we annotate the expression
with indices:
. These indices aren't
intended to mean anything, but we'll use them for bookeeping as we develop the grammar. For each set of productions, we denote any starting symbol
S as
. If any nonterminal and its productions can be
eliminated because it is unreachable from the starting symbol, it is
marked with
.



Thus the final grammar constructed is:
-
.
.
Each production is used once.
-
.
-
With start symbol
the grammar is:

The meaning of
is that the number of a's generated by
is
equal to
.
-
The fact we are trying to prove is that if
has
an equal number of a's as b's then
. This
will be proved by induction on n where |x| = 2n.
-
The basis is n=0. The only string of length 0 is
.
in one step.
-
The inductive hypothesis is: If w is a string in
with an equal
number of a's as b's and |w| < 2n, then
.
-
Case 1 of the induction step. Recall that we are assuming that
x has an equal number of a's as b's, |x| = 2n and n > 0.
In case 1 there is a string y such that x =yz, y has
an equal number of a's as b's,
, and
.
Since both x and y have an equal number of a's as b's then
it must be the case that z does also.
Since
then |y| < 2n. Since
then it
must be the case that |z| < 2n. Thus, both y and z satisfy the
hypothesis of the inductive hypothesis.
Hence,
and
. By using the
first production with these two derivations we have the derivation.

Next: About this document
James Fix
Mon Feb 5 14:00:23 PST 1996