Foundations of Computer Science
Fall 2007

For today you should have:

1) Read from Sipser and answered the questions below.

2) Worked on the Prolog exercises below.


For next time, you should:

1) Read from Sipser and answer the questions below.

2) Read http://en.wikipedia.org/wiki/Philosophy_of_mathematics

3) Finish the Prolog list exercises.

4) Choose one more Prolog project and write up the problem
   and a solution.

Here's one source of exercises:

http://www.csupomona.edu/~jrfisher/www/prolog_tutorial/2.html


PDA solutions
-------------

parse(I) :- start(S), trans(S, I, []).

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

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

trans(X, I, S) :-
	epush(X, P, Y),
	write(X),
	write(' '),
	write(I),
	write([P|S]),
	nl,
	trans(Y, I, [P|S]).

trans(X, I, [C|D]) :-
	epop(X, C, Y),
	write(X),
	write(' '),
	write(I),
	write(D),
	nl,
	trans(Y, I, D).

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

push(2,0,0,2).
pop(2,1,0,3).
pop(3,1,0,3).

epush(1,$,2).
epop(3,$,4).

start(1).
final(1).
final(4).


I ended up with 5 trans rules:

1) consume input and push
2) consume input and pop
3) null transition and push
4) null transition and pop
5) end of input, check for final state

In theory I might need two more, for transitions that push AND pop
(with and without consuming input).

But enumerating the possibilities is ugly.

Here's an alternative from Thomas Michon (with his comments):

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

% Less code than the DFA!

trans(X, S, Q) :-
	delta(X, CHAR, POP, PUSH, Y),
	append(CHAR, L, Q),
	append(POP, T, S),
	append(PUSH, T, NS),
	trans(Y, NS, L),
	write(Y),
	write(', '),
	write(NS),
	write(', '),
	write(L),
	nl.

trans(X, [], []) :-
	final(X).

% We represent epsilon here as the empty list, and everything else as
% a list containing one character.

% Theoretically, this allows us to define triggers based on
% sequences, which could be interesting.

delta(q1, [], [], [$], q2).
delta(q2, [0], [], [0], q2).
delta(q2, [1], [0], [], q3).
delta(q3, [1], [0], [], q3).
delta(q3, [], [$], [], q4).

start(q1).
final(q1).
final(q4).


Prolog list solutions
---------------------

Here are some to get you started.  We'll do power sets next time.


%reimplementation of the built-in predicate "reverse"
reversed([X|Y],Z,W) :- reversed(Y,[X|Z],W).
reversed([],X,X).

% wrapper predicate to translate from the 3-argument version to
% the 2-argument version
reversed(A,B) :- reversed(A,[],B).

% enumerate pairs of elements from A and B
cross(A,B,[X,Y]) :- member(X,A), member(Y,B).

% anything cross the empty set is the empty set
cross_set(_, [], []).
cross_set([], _, []).

% if the second element is a list, recurse on it
cross_set(A, [C|D], X) :-
	cross_set(A, C, S1), cross_set(A, D, S2), append(S1,S2,X), !.

% the second element is not a list.
% if the first element is not a list, recurse on it
cross_set([A|B], C, X) :-
	cross_set(A, C, S1), cross_set(B, C, S2), append(S1, S2, X), !.

% the first two elements are atoms, so the cross product
% is a list with single pair 
cross_set(A, B, [[A,B]]).


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

Sipser, pages 178-182.


1) What is the difference between M and <M>?



2) What does H do?  What does H stand for?



3) What does D do?  What does D stand for?



4) Why does the non-existence of D imply the non-existence of H?



5) Why is the complement of a decidable language decidable?



6) What technique is used to prove that if A and A-complement
   are recognizable, then A is decidable?



7) On page 142, is it clear that if w is in A, then 
   a recognizer for A must halt and accept w; that is,
   the recognizer can only loop on input that is not in
   the language?



8) Do exercise 4.2 on page 183: "Consider the problem of determining
   whether a DFA and a regular expression are equivalent.  Express
   this problem as a language and show that it is decidable."



9) Do exercise 4.3 on page 183, regarding ALL_DFA




10) Do exercise 4.4 on page 183, regarding A epsilon_CFG