/********************************************
   File: push0.pl     System: SWI-Prolog  5.2.8
   Author: Mihaela Malita
   Date: 10/23/2003
   Title:  A Pushdown Automaton for a^n b^n
       
   Alphabet={a,b} States={s0,s,f} Favorable={s0,f} start is state s0.
    ?- start.
    PushDown accepting a^n b^n
    Input your word:[a,a,b,b].
    s0-a-e-s-a  Stack is: [a]
    s-a-e-s-a  Stack is: [a, a]
    s-b-a-f-e  Stack is: [a]
    f-b-a-f-e  Stack is: []

    Yes
***********************************************/
% t((OldState,Letter,OldTop),(NewState,NewTop)).
   
    t((s0,a,e),(s,a)).   %push a
    t((s,a,e),(s,a)).    %push a
    t((s,b,a),(f,e)).    %pop
    t((f,b,a),(f,e)).    %pop
        
    favorable(s0).           % declare state 3 as favorable
    favorable(f).
    
    start(s0).               % declare state 0 as start state   
          
%  Word is accepted if:
%  Word is finished and Stack is empty and Automaton is in favorable state
    check_word(S,[]):- favorable(S),empty_stack.
    
% If e then push something in the stack    
    check_word(S,[H|T]):-   t((S,H,e),(Q,NewTop)),push(NewTop),
                            write(S-H-e-Q-NewTop),print_stack,nl,
                            check_word(Q,T).
                            
% look at top of stack, find next step if e then pop
    check_word(S,[H|T]):-   look(Top),t((S,H,Top),(Q,e)),pop,
                            write(S-H-Top-Q-e),print_stack,nl,
                            check_word(Q,T).

%   Ask for a word see if it is accepted (yes/no).
    start:- write('PushDown accepting a^n b^n'),nl,
            write('Input your word:'),read(W),
            start(S),check_word(S,W).
            
% declare stack as "dynamic" so you can change it
    :-dynamic(stack/1).         

% initially the stack is empty
    stack([]).

% push something in your stack. Remove old stack and put new stack instead
    push(H):- stack(L),New=[H|L],retract(stack(_)),assert(stack(New)).

% pop something out of the stack. Do not care what
    pop:- stack([_|T]),retract(stack(_)),assert(stack(T)).

% check if stack is empty
    empty_stack:- stack([]).

% print the stack
    print_stack:- stack(L),write('  Stack is: '),write(L).
           
% look at the top of the stack. Do not change stack
   look(Top):- stack([Top|_]).