Foundations of Computer Science
Fall 2007

For today you should have:

1) Done some pleasure reading.

2) Worked on the Prolog implementation of an NFA and a PDA.


For next time, you should:

1) Read from Sipser and answer the questions below.

2) Work on the Prolog exercises below.

3) Prepare for a quiz.


NFA solution
------------

% implementation of N2 on page 51 of Sipser
% Nondeterminism is free!

parse(L) :- start(S), trans(S, L).

trans(X, [A|B]) :-
	delta(X, A, Y),
	write(X),
	write(' '),
	write([A|B]),
	nl,
	trans(Y, B).

trans(X, []) :-
	final(X),
	write(X),
	write(' '),
	write([]),
	nl.

delta(1,_,1).
delta(1,1,2).
delta(2,_,3).
delta(3,_,4).

start(1).
final(4).



% implementation of N4 on page 53 of Sipser
% To implement null transitions, I added epsilon rules
% and a new rule for trans.

parse(L) :- start(S), trans(S, L).

trans(X, [A|B]) :-
	delta(X, A, Y),
	write(X),
	write(' '),
	write([A|B]),
	nl,
	trans(Y, B).

trans(X, L) :-
	epsilon(X, Y),
	write(X),
	write(' '),
	write(L),
	nl,
	trans(Y, L).

trans(X, []) :-
	final(X),
	write(X),
	write(' '),
	write([]),
	nl.

delta(1,b,2).
delta(2,a,2).
delta(2,_,3).
delta(3,a,1).

epsilon(1,3).

start(1).
final(1).


Prolog lists and sets
---------------------

1) Review member, takeout/putin and append from notes13.

   Add the following rules to a file named list.pl, and
   run some queries to test them.

takeout(X,[X|R],R).
takeout(X,[F|R],[F|S]) :- takeout(X,R,S).

putin(X, A, B) :- takeout(X, B, A).

2) Here is a set of rules that defines "perm" such that
   perm(A,B) is true if B is a permutation of the elements
   in A.  Type them in and test them.

perm([X|Y],Z) :- perm(Y,W), putin(X,W,Z).   
perm([],[]).


3) Write a set of rules for "cross" so that cross(X,Y,Z) is
   true if Z is and element of the cross product of sets X and Y.




4) Write a set of rules for "power" so that power(X,Y)
   is true if Y is an element of the power set of X.





5) In each of the previous examples, the rules make it possible
   to enumerate the elements of a set; for example, you can
   enumerate the elements of the cross product of two sets.

   As an alternative, you might want to write rules that generate
   the entire set as a list of tuples.

   Write a set of rules for "cross_set" so that cross(X,Y,Z) is
   true if Z is the cross product of X and Y, represented as a
   set of pairs (which is to say, a list of lists).



6) Similarly, write rules for "power_set" so that power_set(X,Y)
   is true if Y is the power set of X, represented as a list of
   lists.


Exercises 5 and 6 and interesting (at least to me) and challenging 
(at least to me), but I am not sure how useful they are.



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

Sipser, pages 165-178


1) Why should we study unsolvability?




2) On page 166, what do the angle brackets mean?  What type are
   the elements of A_DFA?



3) What algorithm is used to demonstrate the decidability of
   the language in Theorem 4.4?



4) What algorithm is used to demonstrate the decidability of
   the language in Theorem 4.8?



5) Why does the proof that EQ_DFA is decidable fail to prove
   that EQ_CFG is decidable?



6) In the discussion of theorem 4.9, the issue of non-halting
   branches in a non-deterministic PDA should be familiar.  Why?




7) What is the relationship between Theorem 4.7 and Theorem 4.9?




8) How do you show that a set is countable?  How do you show
   that it's not?



9) Which of the following sets are countable?

   a) integers
   b) rational numbers
   c) pairs of integers
   d) k-tuples of integers
   e) real numbers
   f) strings
   g) infinite binary sequences
   h) languages
   i) Turing machines