%----------------------------------------------------------------
% this time we do the delta transition functions as
% a nondeterministic finite automaton
%
% nondeterminism is perfect for prolog
% why??
%----------------------------------------------------------------


%----------------------------------------------------------------
%  First, define the basic machine behavior... 
%  this part is common to all FSA definitions
%----------------------------------------------------------------

%--- vocal running... show the parse ----------------------------

parse(Word) :- start(St), crank(St,Word).

crank(St,[]) :- final(St), write(St), write('  '), write([]), nl.

crank(St,[H|T]) :- delta(St,H,Nx),
                   write(St), write('  '), write([H|T]), nl,
                   crank(Nx,T).

%--- silent running... just say yes or no -----------------------

accept(Word) :- start(State), run(State,Word).
run(State,[])     :- final(State).
run(State,[X|Xs]) :- delta(State,X,Next), run(Next,Xs).


%-----------------------------------------------------------------
% Now, this specific FSA graph definition
% this is the data table for the generic machine above
% 
% language: a ( b*| c*) d
%-----------------------------------------------------------------

start(0).
final(3).

delta(0,a,1).
delta(0,a,2).
delta(1,c,1).
delta(1,d,3).
delta(2,b,2).
delta(2,d,3).

%-----------------------------------------------------------------
% draw the diagram... it will help you see the language
%-----------------------------------------------------------------