Date: Wed, 08 Jan 1997 20:36:50 GMT Server: NCSA/1.4.2 Content-type: text/html CSE 322: Assignment 9 Solution Set



next up previous
Next: About this document

CSE 322 Winter 1996: Assignment 9 Solution Set

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

    Let where for all , ,

    Behavioral Lemma: For all , , , , and , if and only if and .

  2. Suppose is regular. If we intersect L with any regular language, the resulting language is also regular. For instance, is regular. But , and we know that this language is not regular from class. This is a contradiction so L must not be regular.

  3. Show that the language is not regular.

    Assume L is regular, and let be a DFA that accepts L. Suppose Q contains n states. Consider the computation of M on any string of length n or more. Because there are only n total states, some state will be visited more than once during the computation. For example, when M processes the string , the computation looks like this:

    for some , , and . Because we visit the same state twice, we can remove from the string and still end in the same state:

    This means that . However, . Also, note that since and , 2n+1 must be greater than j-i. This means that . So falls strictly between and , two consecutive perfect squares. Therefore, is not a perfect square and . This is a contradiction, so L must not be regular.





James Fix
Wed Mar 6 11:11:44 PST 1996