Date: Wed, 08 Jan 1997 20:40:03 GMT Server: NCSA/1.4.2 Content-type: text/html CSE 322 Assignment 7 Due Friday, February 16, 1996



next up previous
Next: About this document

CSE 322 Assignment 7 Due Friday, February 16, 1996

  1. Let be a regular grammar which only has production of the form and . Consider the NFA where is a production in and is a production in .
    1. Carefully prove the behavioral lemma: For all , and , if and only if . Your proof should be brief, but complete. (Hint: there are two induction proofs, one for each direction in the if and only if statement.)
    2. Use the behavioral lemma to prove that .
  2. Number 12 on page 164.
  3. Number 13 (c) on page 165.
  4. Number 21 on page 165.





James Fix
Wed Feb 14 14:37:27 PST 1996