Name:

No books, notes, or scratch paper. Use pen or pencil, any color. Use the rest of this page and the backs of the pages for scratch paper. If you need more scratch paper, it will be provided.

The entire test is 150 points.}

1. True or False. [5 points each]

   1. The intersection of any two regular languages is regular.
   2. If L is any regular language, define PREF(L) to be the set of all prefixes of strings in L. (A prefix of a string w is a substring consisting of the first k symbols of w, for some k.) Then PREF(L) is regular.
   3. Every subset of a regular language is regular.
   4. If h is a homomorphism Sigma --> Gamma*, and if L is a language over Sigma such that h(L) is regular, then L must be regular.
   5. Let M be a finite state machine with both input and output, where the input alphabet is Sigma and the output alphabet is Gamma. Let L be a regular language over Sigma, and let M(L) be the language over Gamma consisting of all possible output strings providing the input string is in L. Then M(L) must be regular.
2. Give a definition of each of the following terms. Giving an example does not help. [10 points each]

   1. Deterministic, as in "deterministic machine." No more than 10 words.
   2. The Kleene closure of a language.
   3. Regular set of natural numbers.
   4. Pigeonhole principle.
3. [15 points] Draw an NFA which accepts the language over {0,1} described by the regular expression

   (0+1)*(00101+0110+11011)(0+1)*

4. [20 points] State the pumping lemma for regular languages.
5. [20 points]Construct the unique minimal DFA equivalent to the NFA drawn here.

   (Missing diagram)

6. [30 points] You learned in class that the language {a^nb^n | n >= 0} is not regular. Using this fact, and other facts you have learned, prove that the language over {0,1} consisting of all strings which have exactly twice as many 0's as 1's (such as the strings 001, 010, 101100000, for example) is not regular. (Hint: do not try to use the Pumping Lemma.)