Foundations of Computer Science
Fall 2007

For today you should have:

1) Finished your DFA/NFA implementation and brought hardcopy.

2) Prepared for the exam.

3) Read from Sipser and answered the reading questions in notes09.txt


For next time, you should:

1) Read from Sipser and answer the questions below.


Reading questions
-----------------

Sipser, pages 109-123, for Thursday 4 October

1) What is the feature of a PDA that makes it capable of
   recognizing a language like O^n1^n when a DFA cannot?




2) In the formal definition of a PDA why is the stack alphabet
   different from the input alphabet?




3) If you were implementing the transition function \delta as
   a dictionary in Python, what type would the keys have?
   What type would the values have?




4) In figure 2.15, what is the sequence of states the PDA
   goes through while parsing 0101?




5) In constructing PDAs, what is the role of the special symbol $?




6) What are the two steps in proving that a language is
   context free iff a PDA recognizes it?




7) What kind of proof is given for Lemma 2.21 on page 115?




8) What kind of proof is given for Lemma 2.27 on page 119?




9) Why do we need the two "claims" on page 121?




[On page 122, the end of the proof is pretty abrupt -- you have
 to unwind the stack to see that the proof is complete.]


10) Do exercise 2.1 on page 128.




11) Do exercise 2.3 on page 128.