Foundations of Computer Science
Fall 2007

For today you should have:

1) Read from Sipser and answered the questions in notes10.

2) Worked on your parzzer.

3) Prepared for a quiz.


For next time, you should:

1) Read from Sipser and answer the questions below.

2) Finish your parzzer.

3) Install gprolog and start on the warmups below.


Parzz discussion
----------------

1) Let's say you are trying to match parentheses.  What's wrong
with the following grammar (as on page 103):

S -> aSb | SS | e

What can we do to solve this problem?


2) Strategies for building the parse tree?


Practical parsing is a major topic in a compilers class.

1) Bottom-up parsing works for a subset of CFLs called LR
   because they can be parsed Left-to-right and produce a 
   Rightmost derivation.

   The most common algorithm is called a shift-reduce parser.

   The basic operations are

   a) input tokens are scanned one at a time and pushed onto a stack

   b) when the top elements of the stack match a rule, they are
      popped and replaced by a variable

   It can take some effort to re-write a CFG as an LR grammar.


2) Top-down parsing works for a smaller subset of CFLs called LL.

   The most natural implementation is a recursive-descent parser.

   The critical property of an LL grammar is that you can look
   at a finite prefix of the input and know which rule to invoke.



Upcoming topics
---------------

1) Declarative programming in Prolog

2) Church-Turing Thesis (Chapter 3)

3) Decidability and the halting problem (Chapter 4)

4) Godel's incompleteness theorem (my materials)

5) Analysis of algorithms (Chapter 7)

6) Algorithms and data structures

   a) hashtables

   b) red-black trees

   c) sets

7) P == NP? (Chapter 7)



Prolog
------

1) Install gprolog

   1a) If you use emacs, you might want to install prolog-mode.


2) Read this page

http://www.dcs.warwick.ac.uk/~mju/CS205/prolog1.html


3) And then download http://wb.olin.edu/focs/harry1.pl

In the usual example, you specify two parents with two different rules,
but (a) that's too much typing, and (b) I wanted to experiment:

% So here are the facts:

parents(lily_evans, james_potter, harry_potter).
parents(petunia_evans, vernon_dursley, dudley_dursley).
parents(molly_prewett, arthur_weasley, ronald_weasley).
parents(molly_prewett, arthur_weasley, ginevra_weasley).
parents(cedrella_black, septimus_weasley, arthur_weasley).

% And here's the first set of rules:

mother(X,Y) :- parents(X,_,Y).
father(X,Y) :- parents(_,X,Y).

% The underscore is an anonymous variable, loosly translated "anyone"

% A comma between rules is AND.
% A semi-colon between rules is OR.

parent(X,Y) :- mother(X,Y); father(X,Y).

% You can have more than one anonymous variable; they don't
% have to match.

mother(X) :- parents(X,_,_).
father(X) :- parents(_,X,_).

% you can combine rules and facts

male(X) :- is_father(X).
male(harry_potter).
male(dudley_dursley).

female(X) :- is_mother(X).
female(ginevra_weasley).


4) Start gprolog and "consult" this file:

$ gprolog
GNU Prolog 1.2.18
By Daniel Diaz
Copyright (C) 1999-2004 Daniel Diaz

| ?- [harry1].

compiling harry1.pl for byte code...
harry1.pl compiled, 24 lines read - 2569 bytes written, 18 ms

yes
| ?- 


5) Try out the following queries:

   a) True/False

| ?- female(lily_evans).

yes

   b) One reply.

| ?- mother(lily_evans, X).

X = harry_potter

yes


   c) Multiple replies.

| ?- parents(molly_prewett, arthur_weasley, X).

X = ronald_weasley ? a

X = ginevra_weasley

yes

	After the first reply, you can press return to quit
	or 'a' to get 'all' replies.


   d) No replies

| ?- parent(harry_potter, X).

no



6) Answer the following questions by formulating appropriate
   queries:

   a) Is Harry Potter male?

   b) Is Harry Potter a father?

   c) Who are the children of Petunia Evans?

   d) Who is Harry Potter's father?

   e) Who are Molly Prewett's children?


7) Add a rule to define grand_parent(X,Y) and use it to
   find the grandparents of Ronald Weasley.

8) Add a rule to define ancestor(X,Y) and use it to find the
   ancestors of Harry Potter.


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

Sipser, pages 137-

1) What are the differences between a Turing machine and a
   finite automaton?




2) If you were using a Python dictionary to represent the
   transition function, delta, for a Turing machine, what
   type would the keys and values be?




3) What is a configuration of a Turing machine?




4) What does it mean to say that one configuration yields another?




5) What is the difference between Turing-recognizable and
   Turing-decidable?




6) At the bottom of page 147, Sipser claims that languages
   A, B, C, and E are decidable.  What is the basis of this claim?




7) What happened to language D?




8) Do exercise 3.1 on page 159, at least until you get sick of it.