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 up previous
Next: About this document

CSE 322 Midterm Solutions Winter Quarter, 1996

  1. 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:

  2. .

    . Each production is used once.

  3. .

  4. With start symbol the grammar is:

    The meaning of is that the number of a's generated by is equal to .

  5. 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.
    1. The basis is n=0. The only string of length 0 is . in one step.
    2. The inductive hypothesis is: If w is a string in with an equal number of a's as b's and |w| < 2n, then .
    3. 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 up previous
Next: About this document



James Fix
Mon Feb 5 14:00:23 PST 1996