Foundations of Computer Science
Fall 2007

For today you should have:

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


For next time, you should:

1) Read from Sipser and answer the questions below.

2) Work on your parzzer.


Exam report
-----------

Most questions scored out of 6, except Questions 2.3, 2.4,
3.1, 3.2, 3.3, all out of 3.  Total points = 57.

Overall, pretty good.  Very roughly:

50s = some kind of A
40s = some kind of B
30s = some kind of C

That is, if this was the only grade to go on.

Part One:

Good job on the DFA/NFA.

To prove something regular:

1) show how to construct a DFA/NFA

2) show how to construct a regular expression

3) converse of pumping lemma?

   If all strings (len>p) in A can be pumped => A is regular

   where "can be pumped" means that there exists at least
   one way of dividing it into xyz such that xy^iz is in A.

4) one string that can be pumped does not a regular language make!


To prove that something is not regular:

1) use the pumping lemma, but be careful and explicit

   careful = you have to show that there is at least one
             string that cannot be pumped, which means that
	     there is _no_ way to divide it.

   explicit = spell out the whole argument

	      a) assume A is regular
	      b) show a string that can't be pumped
	      c) contradiction implies that A is not regular.

2) intuition can only get you so far

   You should have an idea of what kinds of things a DFA can't do.

   But be careful, for example:

   A = { w | w contains the same number of 01 and 10 as substrings}

   Proof that A is not regular:

   1) strings in A can be arbitrarily long, so they can contain any
      number of 01 and 10 substrings

   2) a DFA cannot count arbitrarily high

   3) therefore A is not regular

   [Note to anyone who reads these notes without coming to class:
   this proof is bogus; A is regular.]



Part Two:

(define (bignum-to-int t)
  (if (null? t) 0
      (+ (car t) (* 10 (bignum-to-int (cdr t))))))


(define (poly coeffs)
  (lambda (x)
    (if (null? coeffs)
        0
        (+ (car coeffs) (* x ((poly (cdr coeffs)) x))))))

Comments:

1) Some of you are tail recursion junkies.  

2) A solution that involves exponentiation is not very elegant.


Part Three:

Evaluating the lambda calculus is tricky!

Don't forget eta-reduction:  L x. f x -> f

NAND := L x y. x (y FALSE TRUE) TRUE

NAND := L x y. x y FALSE FALSE TRUE

EXP := L m n. n (MULT m) ONE

What do we think of:

EXP  := L m n. Y EXPS m n

EXPS := L f m n. IFTHENELSE (ISZERO n) ONE (MULT m (f (PRED n)))


The Lexx
--------

http://wb/focs/solutions/lexx.py


1) lexx1.py had a bug, which is that NFA inherited DFA.copy, which
   did not copy the nulltrans attribute.  

2) DFA.process is simple because we did all the hard work when we
   built the DFA.

3) NFA.process is complicated because it never really builds the DFA.


The Parzz
---------

Your next mission is to write a parser by implementing a PDA in Python.

I would like you to work in the following pairs:

   Andy     Ben 
   Yifan    Avi
   Thomas   Liana
   Vito     Doug
   Kent     Evan
   Jeff     Brad

I won't give you starter code this time, but in class we will discuss
implementation choices.  Broadly, you have two options:

1) Implement a PDA as in Definition 2.13 (page 111)
   using appropriate data structures and then process input
   using an algorithm similar to NFA.process in lexx.py

2) Implement the algorithm in the informal PDA description on page 116.
   If you choose this option, you will have to think about how to
   implement the nondeterminism.


This assignment comes in two flavors, basic and advanced:

1) Basic: write a function called Grammar.process that takes
   a string and returns 'accept' if the string is in the language
   described by the Grammar, and 'reject' otherwise.

2) Advanced: extend your function to return a parse tree for the
   string, if it exists, or None otherwise.

   Extra advanced: if the Grammar is ambiguous, you might want
   to return more than one parse tree.


What grammar should you implement?

1) Basic: start with something simple like Example 2.3 on page 103

2) Intermediate: implement something like Example 2.4 on page 103.

3) Advanced: write a grammar for the lambda calculus and implement
   a parser for it.


You will definitely need a Stack and might need a Queue.  Here
is an implementation you can use:

class Sequence:
    """the parent class for Stack and Queue"""
    def __init__(self):
        self.elts = []

    def not_empty(self):
        return self.elts

    def push(self, elt):
        self.elts.append(elt)

class Stack(Sequence):
    """a first-in last-out stack"""
    def pop(self):
        return self.elts.pop(-1)

class Queue(Sequence):
    """a first-in first-out queue"""
    def pop(self):
        return self.elts.pop(0)



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

Sipser, pages 123-132

1) How are the conditions for the CFL pumping lemma different
   from the conditions for the RL pumping lemma?




2) How do you compute p for a given CFG?




3) In the proof of the CFL pumping lemma, why do we choose the
   parse tree with the fewest nodes?




4) In the proof of the CFL pumping lemma, why do we choose the
   lowest |V| + 1 variables in the path?




5) Looking at the examples on pages 126 and 127, can you give
   an intuitive explanation of what PDAs cannot do and why?




6) Do exercise 2.4 on page 128.




7) Do exercise 2.9 on page 129.




8) Read exercise 2.15 and then do exercise 2.16 on page 129.