CS 46 Midterm exam on Wednesday, 4 Mar. in class.

Due: Wednesday, Feb. 18

1. Write solutions to: 3.5.2a,b (you can use our in class version of the Pumping Lemma for CFLs which is essentially the same as the version in ex. 3.5.7), and three more from: 3.3.4 (part a should ask you to show Le(M')=L(M) union {e} because accepting by empty stack always accepts the empty string; hint: you might want to introduce a 'new' stack symbol used to indicate the bottom of the stack), 3.5.1, 3.5.4, 3.5.8,3.5.10 (part a should ask you to prove that L(G')=L(G)-{e}), 3.5.k (2PDA immediately below)

   3.5.k. A 2-way PDA (2PDA) is a PDA whose input head is allowed to move either way on the input tape. It starts at the left end of the input tape and accepts any string for which the 2PDA moves off the right end of the string in an accepting state. Show that the language L = { 1^k2^k3^k | k > 0 } is accepted by a 2PDA.
   This is interesting because if you recall from Example 3.5.2 on page 146, L is NOT context-free. So, 2PDAs are strictly more powerful than ordinary PDAs. It is also interesting because 2DFAs are no more powerful than an ordinary DFA (cf. below).

2. For those looking for a fun challange (not required of anyone)
   Take a couple of passes through reading problem 2.5.4 until you get dizzy. If it seems trivial, either you don't understand or you are a born theorist. I am not asking you to write up a solution to this, although if you have time on your hands, you may find this an interesting challange. A pebble-automaton is a 2-way DFA that can drop a pebble on any input square and sense whether a square holds the pebble. If you knock off 2.5.4, you might try to formalize a definition of a pebble automaton and then prove that any language that can be accepted by a pebble automaton can be accepted by an ordinary, one-way DFA. This is interesting because it shows that 2-way tape head motion (even with the ability to mark a square and come back to it) does not add to the power of a DFA (in terms of what can be accepted).