Computer Science 456/656 Fall 2001 Second Examination, November 20, 2001

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

1. True or False. [5 points each] (a) Every context-free language over the unary alphabet {1} is regular.

(b) Every subset of a regular langauge is regular.

(c) Every context-free language that does not contain the empty string has a Chomsky Normal Form grammar.

(d) The intersection of context-free language with any regular language is context-free.

(e) Every language that can be accepted by a PDA has an unambiguous context-free grammar.

(f) No Turing Machine can solve the halting problem. However, more sophisticated machines can solve the halting problem.

(g) Let L be the language of all palindromes over {a, b}. L is inherently ambiguous.

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

(a) If there is an procedure to solve a problem, there is a machine which solves that problem.

(b) A bottom-up parser is also called a  -  parser.

3. [20 points] Given the following grammar, find an equivalent CNF grammar. S → A S → SbS A → aA A → b 4. [20 points] The following grammar generates expressions for a simple programming language. (In this

language, the only variable names permitted are x and y.) S → S + S S → S − S S → S ∗ S S → (S) S → x S → y Give an unambiguous context-free grammar for that same language. Your grammar should be consistent with the usual semantics of algebraic expressions. (Partial credit if your grammar generates the language, but is ambiguous or is not consistent with the semantics.)

5. [20 points] Consider the following context-free grammar, with start symbol S: 1. S → S_{1}

2. S_{1} → AS_{1}

3. S_{1} → Λ

4. A → aA

5. A → b Give a transition table for a deterministic PDA which accepts the language generated by this grammar. (If you decide to use a top-down deterministic PDA, add the rule about ‘$’ to the grammar and to the PDA.)

6. [30 points] Use the pumping lemma for context-free languages to prove that L = {a^{n}b^{n}a^{n}|n ≥ 0} is not context-free.