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]

   1. Any subset of a regular language is a regular language.
   2. The complement of any context-free language is context-free.
   3. The left hand side of a production of any context-free grammar must have exactly one symbol.
   4. Every PDA that accepts by final state is equivalent to some PDA that accepts by empty stack.
   5. Every context-free language over the unary alphabet {1} is regular.
   6. It is decidable whether a given CFG generates the empty language.
   7. If G is an ambiguous CFG, then L(G) is definitely not a DCFL.
   8. The set of regular expressions over a given alphabet Sigma is a regular language.
2. Fill in each blank with one word. [5 points each]

   1. The intersection of any context-free language with any _____________ language is context-free.
   2. A _______________ machine has at most one legal move from any configurationa.
   3. The right hand side of any production of any _____________ Normal Form grammar has either one terminal or two variables.
   4. The class of NFA's accepts the class of _______________ languages.
   5. A _____________ is a machine that writes an output string, and given as input w in L, where L is a CFL, it outputs a derivation of w.
3. Give a definition of each of the following terms. [10 points each]

   1. Regular expression over a given alphabet Sigma.
   2. L(M), where M is a non-deterministic machine whose input alphabet is Sigma. (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).
   3. Minimal DFA.
4. [30 points] Let Sigma={a,b,c,+,-,*,/,(,)}. Let L be the language over Sigma of all "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:

   1. G is unambiguous.
   2. 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 Sigma={a,b,c}. Let L = {w in Sigma* | 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.