:- module(_,_,[sr/bfall]).

% Graph example: 
% Definition of a (generic) Non-deterministic PushDown Automaton
% (NPDA, automaton with stack): 

npda_accept(S) :- 
    npda_initial(Q),
    npda_accept_from(S, Q, []).

npda_accept_from([], Q, [])  :-
    npda_final(Q).
npda_accept_from([C|Cs], Q, Stack) :-  
    npda_delta(Q, C, Stack, NewQ, NStack),
    npda_accept_from(Cs, NewQ, NStack).

% A concrete automaton, defined by its initial and final states: 
npda_initial(q0).     
npda_final(q1).
% and its transitions:
npda_delta(q0, C,     Stack, q0, [C|Stack]).
npda_delta(q0, C,     Stack, q1, [C|Stack]).
npda_delta(q0,_C,     Stack, q1,    Stack ).
npda_delta(q1, C, [C|Stack], q1,    Stack ).

% Try:
% Check if these sequences accepted: 
% ?- npda_accept([a,b,b,a]).
% ?- npda_accept([a,b,c,b,a]).
% ?- npda_accept([a,b,c,c,b,a]).
% ?- npda_accept([a,b,X,a]).
% List all sequences of 4 chars: 
% ?- npda_accept([A, B, C, D]).
% List all accepted sequences: 
% ?- npda_accept(X).

% What is the name of the sequences it recognizes? 

% Alternative: accept only words formed with symbols of 
%              a particular alphabet.
 
npda_accept_alt(S) :- 
    npda_initial_alt(Q),
    npda_accept_from_alt(S, Q, []).

npda_accept_from_alt([], Q, [])  :-
    npda_final_alt(Q).
npda_accept_from_alt([C|Cs], Q, Stack) :-  
    npda_delta_alt(Q, C, Stack, NewQ, NStack),
    npda_accept_from_alt(Cs, NewQ, NStack).

% A concrete automaton, defined by its initial and final states: 
npda_initial_alt(q0).     
npda_final_alt(q1).

npda_delta_alt(q0, C,     Stack, q0, [C|Stack]) :- symbol(C).
npda_delta_alt(q0, C,     Stack, q1, [C|Stack]) :- symbol(C).
npda_delta_alt(q0, C,     Stack, q1,    Stack ) :- symbol(C).
npda_delta_alt(q1, C, [C|Stack], q1,    Stack ) :- symbol(C).
symbol(a).
symbol(b).
symbol(c).

% Try:
% Check if these sequences accepted: 
% ?- npda_accept_alt([a,b,b,a]).
% ?- npda_accept_alt([a,b,c,b,a]).
% ?- npda_accept_alt([a,b,c,c,b,a]).
% ?- npda_accept_alt([a,b,X,a]).
% List all sequences of 4 chars: 
% ?- npda_accept_alt([A, B, C, D]).
% List all accepted sequences: 
% ?- npda_accept_alt(X).