Computer Science 456/656 Spring 1997 Midterm February 12, 1997

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 170 points.

1. True or False. [2 points each] For each incorrect answer, 2 points will be subtracted.

(a) The union 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) The set of algebraic expressions (those that would be accepted by your high-school math teacher) is a regular language.

(e) The set of base 7 numerals that name multiples of 17 is regular.

2. Fill in each blank with one word. [5 points each]

(a) Every NFA with n states is equivalent to a unique DFA, which has at most states. (I want the formula.)

(b) According to the principle, if there is a function from A to B, and if A has more elements than B, then there must be at least two elements of A that are mapped to the same element of B.

(c) We use the principle to prove that a predicate is a tautology by first proving a basis and then proving each case follows from its immediate predecessor.

3. Give a definition of each of the following terms. If you more than fill the space given, you are most certainly writing too much. [10 points each]

(a) Language

(b) The Kleene closure of a language L.

(c) Pumpable substring of a string w, with respect to a language L.

(d) Language accepted by a non-deterministic machine M.

(e) Symbol.

4. What language (describe it simply in English) does the regular expression (b + ab)^{∗}(a + Λ) describe? (I can write the description in eight words.) [15 points]

5. Draw a minimal deterministic FA which accepts the language of all strings over {a, b} which do not contain the substring abb. [15 points] 6. Use the pumping lemma directly to prove that the set of strings over the alphabet {1} which represent

perfect squares in unary (“caveman”) notation is not a regular language. [30 points] 7. The Fibonacci numbers are the numbers in the following sequence: 0, 1, 1, 2, 3, 5, 8, 13, … where each

number, after the first two, is the sum of its two immediate predecessors. Let L be the language of all strings over {0, 1} which do not contain the substring 11. Thus, L = {Λ, 0, 1, 00, 01, 10, 000, …} For any n ≥ 0, let f(n) be the number of strings in L which have length n. Prove that for each n, f(n) is a Fibonacci number. [30 points]