Computer Science 456/656 Fall 1998 Midterm, October 15, 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 175 points.

1. True or False. [5 points each] (a) Any subset of a regular language is a regular language.

(b) The intersection of any two context-free languages is context-free.

(c) The language {a^{i}b^{i} : i ≥ 0} does not have an ambiguous grammar.

(d) The set of all regular expressions over the alphabet {0, 1} is a regular language.

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

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

(b) The intersection of any CFL with any language is a CFL.

3. What does the CKY algorithm do? [10 points]. Just answer the question, do not give an example.

4. Draw a minimal DFA which accepts the language of all strings over {0, 1} which contain at least two instances of 01 as a substring. [15 points] 5. Let G be the CFG whose productions are given below:

S → Λ S → aSb S → bSa S → SS

(a) Prove that all strings in L(G) have equal numbers of a’s and b’s. [10 points]

(b) Prove that all strings over {a, b} which have equal numbers of a’s and b’s are in L(G). [15 points] 6. Let L_{1} = {a^{i}b^{i}a^{i} : i ≥ 0}. Let L_{2} be the complement of L_{1}, i.e., all strings over {a, b} which are not

in L_{1}. Prove that L_{2} is not a CFL, or prove that it is. [30 points] 7. Consider the grammar G whose terminal alphabet is {(,), +, −, a, b}, whose variables alphabet is {S, T, V },

and whose productions are: S → S + T S → S − T S → T T → V T → (S) V → aV V → bV V → a V → b

(a) Construct a parse tree for the string a − b − ab − (bb + ab − aa). [15 points]

(b) Construct a CNF grammar equivalent to G. [15 points] 8. Let L be the set of all strings over {a, b} which have equal numbers of a’s and b’s. Use the pumping

lemma to prove that L is not regular. [30 points]