Date: Wed, 08 Jan 1997 20:39:25 GMT Server: NCSA/1.4.2 Content-type: text/html CSE 322 Assignment 7 Solution Set Wednesday, February 21, 1996



next up previous
Next: About this document

CSE 322 Assignment 7 Solution Set Wednesday, February 21, 1996

    1. () First we'll show that for all and , if , then for all by induction on n:

      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 .

    2. Proof that :

      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 .

  1. Number 12 on page 164.

    1. The state transition table of M:

    2. All the possible computations of the string aaabb are given below. Computations that terminate with errors (those that have no successor configurations and have not processed the entire input string) are marked with :

    3. Since is a final state and , the string aaabb is in .

    4. is one regular expression that describes . This comes from the fact that you can get to with a string of the form or . From , we can hop to and back to with any number of times. This describes all the possible paths to , so we have which simplifies to the above regular expression.

  2. Here is an NFA that accepts exactly the strings described by :

  3. Here is a DFA that accepts the strings ending in abaa:

    Here is an NFA with 6 transitions that accepts the same:





next up previous
Next: About this document



James Fix
Wed Feb 21 14:07:42 PST 1996