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

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

(b) The complement of any context-free language is context-free.

(c) The left hand side of a production of any context-free grammar must have exactly one symbol.

(d) Every PDA that accepts by final state is equivalent to some PDA that accepts by empty stack.

(e) Every context-free language over the unary alphabet {1} is regular.

(f) It is decidable whether a given CFG generates the empty language.

(g) If G is an ambiguous CFG, then L(G) is definitely not a DCFL.

(h) The set of regular expressions over a given alphabet Σ is a regular language.

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

(a) The intersection of any context-free language with any language is contextfree.

(b) A machine has at most one legal move from any configuration.

(c) The right hand side of any production of any Normal Form grammar has either one terminal or two variables.

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

(e) A is a machine that writes an output string, and given as input w ∈ L, where L is a CFL, it outputs a derivation of w.

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) Regular expression over a given alphabet Σ.

(b) L(M), where M is a non-deterministic machine whose input alphabet is Σ. (You are not told whether M is an NFA, or a PDA, or a TM, or some other kind of machine that we have not discussed yet.) Your answer should contain the word “configuration” or the phrase “instantaneous description” (these mean the same thing).

(c) Minimal DFA.

4. [30 points] Let Σ = {a, b, c, +, −, ∗, /, (,)}. Let L be the language over Σ that are “valid” algebraic expressions, where variables are always a single letter, where ∗ and / are used to denote multiplication and division, and where + and − always mean addition and subtraction (that is, there is no unary operator). Construct a CFG G which generates L, and which has the following additional properties:

(a) G is unambiguous.

(b) The parse tree over G of any string w in L respects the usual semantics of the string. That means that if a, b, and c have stored values, then every internal node in the parse tree has a value which is derivable from the values of its children in the obvious way, in such a manner that the value at the root is the value of w interpreted as an expression. You must be careful to keep in mind that multiplication and division have precedence over addition and subtraction, and that among operators of equal hierarchy, the leftmost has precedence.

5. [25 points] Let Σ = {a, b, c}. Let L = {w ∈ Σ^{⋆} : n_{a}(w) = n_{b}(w) = n_{c}(w)}. (For example, the string aaababccbcacbcb is in L.) Is L a context free language? If so, construct a CFG which generates L. If not, give a proof that L is not context-free.