CS 254: Automata and Computability

Takehome exam. Due on paper 5:00PM Monday, 7 June 2010.

This is an open-notes, open-Internet, open-book exam, with two restrictions: (1) you may not consult with people other than Jeff Ondich about the exam, and (2) if you encounter solutions to Kozen's problems anywhere, you need to avert your eyes and ignore them.

  1. (8 points) Let A = {a2nbn | n ≥ 0}. Is A regular? Context-free but not regular? Recursive but not context-free? Prove your answer.
  2. (8 points) Do problem #2 on page 309 of Kozen.
  3. (8 points) Consider exercise #108 on page 343 of Kozen. Pick exactly two of the four problems in this exercise, one decidable and one undecidable, and provide proofs that your choices are correct.
  4. (8 points) Do problem #125 on page 346 of Kozen. This may require you to read a little bit about context-sensitive grammars (see page 258).
  5. (2 points) What interesting thing in the computing world should I read about this summer?

  6. (8 points) Consider Wikipedia's discussion of LR parsing, from which I adapted my lecture last Friday.

    Can you modify the algorithm and/or the grammar described under "General case" and "Concrete example" so that the algorithm would not just accept or reject input strings, but would (in the case of accepted strings) also output the arithmetic value of the input? How? (The smaller the modification, the better.)

    Note that you may need to modify the grammar's productions to support operator precedence. If you do so, then you should use the procedure described under "Constructing LR(0) parsing tables" to compute the new grammar's Action and Goto tables.