Computer Science 456/656 Spring 1999 Second Examination, March 22, 1999

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. [5 points each] (a) Most of the usual programming languages in use, including C++, are context-free.

(b) Every context-free language that does not contain the empty string is generated by a Chomsky Normal Form grammar.

(c) Every subset of a regular set of integers is regular.

(d) A language L is context-free if and only there is some PDA that accepts L.

(e) A language L is context-free if and only there is some DPDA that accepts L$.

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

2. Fill in each blank with one word. [5 points each blank] (a) An LL parser produces a leftmost of the input string.

(b) A - [two words] parser gives a bottom-up parsing of the input string.

(c) The problem of whether two context-free grammars generate the same language is .

3. Let L be the language over {0, 1} consisting of all strings which have at least twice as many 0’s as 1’s. Prove that L is a context-free language. [30 points] 4. Let L be the language over the alphabet Σ = {a, b} generated by the context-free grammar G given

below. The start symbol of G is E. [10 points each part] E → E + E | EE | E − E | − E | (E) | a | b

(a) Give a leftmost derivation of the string a(b + a)(−a), using G.

(b) Draw a derivation tree (parse tree) for the string a(b + a)(−a), using G.

(c) Prove that G is ambiguous.

5. Let L be the language over {0, 1} consisting of all strings of the form 0^{i}1^{i}0^{i}, for i ≥ 0. Prove that L is not a context-free language. [30 points] 6. Let L be the context-free language over the alphabet Σ = a, b generated by the grammar G with start

symbol S, and with productions given below. Find an unambiguous Chomsky Normal Form grammar that also generates L. [30 points] (Partial credit if you find an ambiguous CNF grammar.) Hint: the grammar you need is considerably more complex than G. I can do it with 5 variables and 9 productions. Maybe you can do better.

1. S → ab

2. S → SS

3. S → aSb