Computer Science 456/656 Spring 1998 Midterm February 18, 1998

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]

(a) The intersection of any two regular languages is regular.

(b) 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.

(c) Every subset of a regular language is regular.

(d) If h is a homomorphism Σ → Γ^{⋆}, and if L is a language over Σ such that h(L) is regular, then L must be regular.

(e) Let M be a finite state machine with both input and output, where the input alphabet is Σ and the output alphabet is Γ. Let L be a regular language over Σ, and let M(L) be the language over Γ 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. If you more than fill the space given, you are most certainly writing too much. Giving an example does not help. [10 points each]

(a) Deterministic, as in “deterministic machine.” No more than 10 words.

(b) The Kleene closure of a language L.

(c) Regular set of natural numbers.

(d) Pigeonhole principle.

3. Draw an NFA which accepts the language over {0, 1} described by the regular expression

(0 + 1)^{⋆}(00101 + 0110 + 11011)(0 + 1)^{⋆}

[15 points]

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

2 6. You learned in class that the language {a^{n}b^{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.) [30 points]