- Answer the problems on the exam pages.
- There are thirteen problems for 120 total points plus 10 extra credit. Actual scale was A=112, C=70.
- If you need extra space use the back of a page.
- No books, notes, calculators, or collaboration.
- The first six questions are true/false, with five points for the correct boolean answer and up to five for a correct justification of your answer -- a proof, counterexample, quotation from the book or from lecture, etc. -- note that there is no reason not to guess if you don't know.

Q1: 10 points Q2: 10 points Q3: 10 points Q4: 10 points Q5: 10 points Q6: 10 points Q7: 10 points Q8: 10 points Q9: 10 points Q10: +10 points Q11: 10 points Q12: 10 points Q13: 10 points Total: 120+10 points

The regular language L_{1} is over the alphabet Σ =
{a, b, c} and is defined by the regular expression
Σ^{*}(aa ∪ bb ∪ cc)Σ*.

The language L_{2} is the complement of L_{1}, that
is, Σ* ∖ L_{1}.

The context-free language L_{3} over the alphabet {a, b} is
defined by the grammar with start symbol S and rules S → bSS and
S → a.

**Question 1 (10):***True or false with justification:*The class of context-free languages is closed under reversal. That is, if L is any context-free language, then the language L^{R}= {w^{R}: w ∈ L} is context-free.**Question 2 (10):***True or false with justification:*The language L_{4}= {a^{i}b^{j}c^{k}: (i ≥ (i + j + k)/117) ∧ (j ≥ (i + j + k)/117) ∧ (k ≥ (i + j + k)/117)} is a context-free language.**Question 3 (10):***True or false with justification:*Let u and v be any two nonempty strings. Then u and v are L_{1}-equivalent (in the sense of the Myhill-Nerode Theorem) if and only if u and v have the same last letter.**Question 4 (10):***True or false with justification:*The language L_{3}has exactly four strings of length 7.**Question 5 (10):***True or false with justification:*Let u, v, x, y, and z be any five strings over the same (nonempty) alphabet. Then the language {uv^{i}xy^{i}z: i ≥ 0} is a context-free language.**Question 6 (10):***True or false with justification:*Let N be an NFA, with no ε-moves, all of whose states are reachable from the start state. Let D be the equivalent DFA constructed from N by the Subset Construction, containing only states reachable from its start state. Then D must have at least as many states as N.Questions 7-10 use the languages L

_{1}and L_{2}defined above.**Question 7 (10):**Build and NFA whose language is L_{1}. Justify your answer. (Note: The construction from Sipser gave 22 states (by my count) for this regular expression. You are welcome to use it, or my simpler construction, but you may be able to create and justify a simpler NFA.)**Question 8 (10):**Build a DFA for the language L_{2}(not for L_{1}) by any valid method.**Question 9 (10):**Give a DFA for L_{2}with the minimum possible number of states, and*prove*that it is minimal. (You could do this by running the minimization algorithm, or by showing that each pair of states is distinguishable.)**Question 10 (10 extra credit):**Give a regular expression for the language L_{2}. (Note -- this is extra credit because it is likely to take some time, so use your best judgement as to whether to try this before attempting the other problems. You could use the book's algorithm to get the regular expression from the DFA. or you could reason directly. Here's a hint if you try the latter -- if w is a string in L_{2}, what can happen between the occurrences of the letter a in w?)Questions 11-13 deal with the context-free language L

_{3}defined above, with the grammar rules S → bSS and S → a.**Question 11 (10):**Give a pushdown automaton whose language is L_{3}, by any valid method.**Question 12 (10):**Is L_{3}a regular language? Prove your answer. (Hint: Consider the intersection of L_{3}with the regular language b^{*}a^{*}.)**Question 13 (10):**Prove carefully that every string in L_{3}has odd length. You should use mathematical induction. One way is to use induction on the number of steps in the derivation of a string in L_{3}. Another is to use the grammar as an inductive definition of the language and use induction on that.

Last modified 26 February 2012