Date: Wed, 08 Jan 1997 20:37:25 GMT Server: NCSA/1.4.2 Content-type: text/html CSE 322 Assignment 9 Due Friday, March 1, 1996



next up previous
Next: About this document

CSE 322 Assignment 9 Due Friday, March 1, 1996

  1. Let and be NFAs. Construct a new NFA M that accepts the language

    Think of L as the set of arbitrary shuffles of strings from and . For example, if aab is in and bb is in then the strings aabbb, ababb, bbaab and many other strings are in L. Hint: The machine will have to run both and in parallel, but only one at a time. Thus, a cross product-like construction is in order.

    You don't have to prove that your construction is correct, but you must state a behavioral lemma which could be used in such a proof.

  2. Show that the set of all strings over the alphabet with an equal number of a's as b's is not a regular set. You may use closure properties of regular languages and the fact that the language is not regular.

  3. Show that the language is not regular. You will have prove this by contradiction from first principles.




James Fix
Tue Feb 27 08:16:35 PST 1996