Foundations of Computer Science
Fall 2007

For today you should have:

1) read from Sipser and answered the questions in notes06

2) finished your translation of the lambda calculus and
   brough a hardcopy of your solution.


For next time, you should:

1) read from Sipser and answer the questions below.

2) Work on the DFA and NFA implementation below.  Teams:

   Jeff	    Brad
   Thomas   Yifan
   Andy K   Liana
   Doug	    Ben F
   Vito	    Avi
   Ilari    Kent   (Ben H)

3) Prepare for a quiz.



DFA and NFA implementation
--------------------------

The following instructions are sparse; you might have to spend
some time reading my code and Chapter 1 to make sense of them.

And, of course, ask questions if you get stuck.


1) Download wb.olin.edu/focs/code/lexx1.py and confirm that you
   can run it.  I think you'll need Python 2.4 or better.


2) Read over the code and make sure you understand the data
   structures involved, especially the sharing model, which is
   a little complicated.


3) Fill in the body of DFA.process and test it.


4) Fill in the body of DFA.union and test it.


5) Now read NFA.null_closure and make sure you understand what
   it does and how it works.


6) Fill in the body of NFA.star and test it.


7) Fill in the body of NFA.process and test it.

   Note: you have two choices here.  You can translate the NFA
   into a DFA and then run DFA.process.  The drawback is that the
   number of states gets very large for any non-trivial NFA.

   The alternative I recommend is to write NFA.process to
   implement the process sketched in Figure 1.29 on page 49.

   You also might want to read the proof on page 55 (including
   the extension to handle null transitions).

   Don't start writing code until you understand what you are
   planning to do!


8) Fill in the body of NFA.union and test it.


9) Fill in the body of NFA.concat and test it.



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

Sipser, pages 67-82

1) For Example 1.56, can you find the equivalent two-state NFA?




2) What is the difference between a GNFA and an NFA?




[If you understand Figure 1.63 and the outline of the proof of
Lemma 1.60, you can skim the formal presentation on pages 73-74.]

3) If a DFA has p states and recognizes a string with length n>p,
   what can we say about the sequence of states that are visited
   when the DFA processes the string?




4) What are the qualitative differences between Sipser's presentation
   of the "proof idea" on page 78 and the "proof" on page 79?




5) To prove that a language is not regular, you only have to
   find one string in the language with a certain set of properties:
   what are they?



[Take your time working through Examples 1.73 through 1.77.  It
takes a while to get comfortable with the logic.]


6) What is "pumping down"?




7) Exercise 1.12 on page 85.




8) Exercise 1.13 on page 85.




9) Exercise 1.29.  Answers for parts (a) and (c) are in the book,
   but you should try several times (at more than one sitting)
   before you give up and look.




10) Exercise 1.30.