Computer Science 456/656 Spring 1997 Midterm March 19, 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 150 points.

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

(a) Any subset of a regular set is regular.

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

(c) The union of any two context-free languages is context-free.

(d) Every PDA is equivalent to some DPDA.

(e) Suppose instead of a stack, a machine has a queue (a structure that stores symbols under

FIFO discipline). Call this a QA. Then, every CFL is accepted by some QA.

2. Fill in each blank with one word. [5 points each] (a) A PDA is essentially the same as an NFA, except that it has a .

(b) The class of right-linear grammars generates the class of languages.

(c) The class of NFA’s accepts the class of languages.

(d) We say that a problem P is if there is no algorithm which decides every instance of P.

(e) Every context-free language which does not contain the empty string is generated by some

normal form grammar.

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) Deterministic. That is, let M be a machine of any class that we have discussed. What does it mean to say that M is deterministic?

(b) Unambiguous (as in, CFG).

(c) Regular Expression over an alphabet Σ

(d) Minimal DFA.

4. Let L = {a^{n}b^{n} : n > 0}. Construct an unambiguous CNF grammar that generates L. [15 points] 5. Let L be the language over Σ = {a, b, c} consisting of all strings with equal numbers of each symbol.

Thus, for example, ababbcacc ∈ L. Use the Pumping Lemma for context-free languages to prove that L is not context-free. [30 points] 6. Give a transition table or a state diagram for a 1-lookahead DPDA that accepts the language L generated

by the context-free grammar whose start symbol is S and whose productions are: S → s S → AS A → aSb [30 points]