%----------------------------------------------------------------
% 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 ( (bc)+ | bc* ) d
%
% try: a b c d d    to show backtracking (it fails, not in lang)
% try: a b c c c d  to show backtracking (it passes, is in lang)
%-----------------------------------------------------------------

start(0).
final(4).

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


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