Foundations of Computer Science
Fall 2007

For today you should have:

1) read from Sipser and answered the questions in notes07.

2) Worked on the DFA and NFA implementation.

3) Prepared for a quiz.


For next time, you should:

1) Finish your DFA/NFA implementation and bring a hardcopy to
   class.

2) Prepare for an exam.

3) Read from Sipser and answer the reading questions below.



Thoughts on the Pumping Lemma
-----------------------------

A good lemma is like a good library function.

It solves a problem that comes up over and over.

It creates an abstraction that is useful for managing complexity.

BUT, it can create a barrier to understanding:

1) In a library the implementation is hidden, which can lead
   to performance errors.

2) In the case of a lemma, you can lose the intuition for
   why the demonstrandum is true.

"Ok, I followed the steps and I 'proved' it, but I still don't 
see why it's true."


A few pumping lemma lemmas:

1) Pumping can only affect the first p symbols in a string.

2) Pumping has to change the length of the string.

3) Pumping can add/remove at most p symbols. 

Do you see how each of these follows from the conditions in
Theorem 1.70 (page 78)?


How would you characterize the languages we have seen that
are not regular?


Lambda calculus solutions
-------------------------

Two suggestions for reading

(define SUCC
  (lambda (n)
    (lambda (f)
      (lambda (x)
        (f ((n f) x))))))

1) Think of it as a function of one argument that returns
   a function of two arguments.

2) Think about what this means:

(define IDENT
  (lambda (n)
    (lambda (f)
      (lambda (x)
        ((n f) x)))))


Similar logic here:

(define PLUS
  (lambda (m)
    (lambda (n)
      (lambda (f)
        (lambda (x)
          ((n f) ((m f) x)))))))

This is a function of two arguments that returns a function
of two arguments.

What does it mean to partially apply a Church numeral?

For this version of MULT, notice the partial application of PLUS.

(define MULT
  (lambda (m)
    (lambda (n)
      ((m (PLUS n)) ZERO))))

For this version, notice that we don't fully unwind the arguments:

(define MULT2
  (lambda (m)
    (lambda (n)
      (lambda (f)
        (m (n f))))))

I throw up my hands at PRED and PRED2.

Read this:

(define CONS
  (lambda (f)
    (lambda (s)
      (lambda (b)
        ((b f) s)))))

As a function of two arguments that returns a function of one argument.

Where are the values f and s stored?


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

Sipser, pages 99-109

1) What is the relationship between a context free grammar and
   a pushdown automaton?




2) What is the difference between a variable and a terminal?




3) Draw the parse tree for the sentence "a boy sees" in grammar G2.




4) What does it mean to say that a string derives another string?
   



5) What strings are in the language of a grammar?




6) What is parsing?




7) What does it mean to say that a grammar is ambiguous?




[You can skim the section on Chomsky normal form, and then stop
at the top of page 109.]