CSc 8710 - Fall 2010
Homework 3
Due: 1 October, 2010
-----------------------

Write a Pushdown Automata (PDA) Simulator in Prolog.
Also, code a PDA for a CFL (different than the one given
below and submit).

NOTE: You may assume the input alphabet to be {a,b}
and the stack alphabet to be {a,b,d}.

Assume a PDA is described using the following predicates: 

  start_state(State).
  delta(FromState,ToState,ReadSymbol,PopSymbol,PushSymbol).
  final_state(State).

For example the following is a PDA description in Prolog:

start_state(q1).
final_state(q1).
final_state(q4).
delta(q1,q2,nil,nil,d).
delta(q2,q2,a,nil,a).
delta(q2,q3,b,a,nil).
delta(q3,q3,b,a,nil).
delta(q3,q4,nil,d,nil).

Note: nil is used to denote the empty string.

The PDA Simulator program will behave as follows under Prolog:

[~/8710][4:27pm] pl
Welcome to SWI-Prolog (Version 3.2.9)
Copyright (c) 1993-1999 University of Amsterdam.  All rights reserved.

For help, use ?- help(Topic). or ?- apropos(Word).

?- ['pda.pl'].
pda.pl compiled, 0.00 sec, 3,196 bytes.

Yes
?- ['anbn.pda'].
anbn.pda compiled, 0.01 sec, 1,556 bytes.

Yes

[raj@tinman f10]$ pl
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 5.6.64)
Copyright (c) 1990-2008 University of Amsterdam.
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.

For help, use ?- help(Topic). or ?- apropos(Word).

3 ?- ['anbn.pl'].
% anbn.pl compiled 0.00 sec, 8,824 bytes
true.

4 ?- ['pda.pl'].
% pda.pl compiled 0.00 sec, 8,824 bytes
true.

5 ?- atom_chars(abaab,L).
L = [a, b, a, a, b].

6 ?- run_pda(aaabbb).
q1:aaabbb:
q2:aaabbb:d
q2:aabbb:ad
q2:abbb:aad
q2:bbb:aaad
q3:bb:aad
q3:b:ad
q3::d
q4::

true .

?- halt.
[~/8710][4:28pm]