/********************************************
   File: pda1.pl     System: SWI-Prolog  5.2.8
   Author: Mihaela Malita
   Date: 10/23/2003
   Title:  A Pushdown Automaton for EQUAL (same number of a's and b's)
       
   Alphabet={a,b} States={q,f} Favorable={f} Start_state= q.
    
    ?- start.
    PushDown accepting EQUAL
    Input your word:[a,b,b,b,a,a,a,a,b,b].
    q-a-c-q-[a, c]  Stack is: [a, c]
    q-b-a-q-e  Stack is: [c]
    q-b-c-q-[b, c]  Stack is: [b, c]
    q-b-b-q-[b, b]  Stack is: [b, b, c]
    q-a-b-q-e  Stack is: [b, c]
    q-a-b-q-e  Stack is: [c]
    q-a-c-q-[a, c]  Stack is: [a, c]
    q-a-a-q-[a, a]  Stack is: [a, a, c]
    q-b-a-q-e  Stack is: [a, c]
    q-b-a-q-e  Stack is: [c]
    q-e-c-f-e  Stack is: []
    
    Yes
***********************************************/
%   t((OldState,Letter,OldTop),(NewState,NewTop))
%   t((s,e,e),(q,[c])).     Special marker in stack initially
    t((q,a,c),(q,[a,c])).   % stack empty push a
    t((q,a,a),(q,[a,a])).   % push a
    t((q,a,b),(q,e)).       % pop if different
    t((q,b,c),(q,[b,c])).   % push b
    t((q,b,b),(q,[b,b])).   % push b
    t((q,b,a),(q,e)).       % pop if different
    t((q,e,c),(f,e)).       % pop     
        
    favorable(f).
    
    start(q).               % declare state s 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  e is on the left  
    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 on right 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).

% look at top of stack, find next step if e then pop
    check_word(S,[H|T]):-   look(Top),t((S,H,Top),(Q,NewTop)),
                            pop,push(NewTop),
                            write(S-H-Top-Q-NewTop),print_stack,nl,
                            check_word(Q,T).
                            
% Jump without condition to another state, stack is unchanged!!
    check_word(S,W):-   look(Top),t((S,e,Top),(Q,e)),pop,
                        write(S-e-Top-Q-e),print_stack,nl,
                        check_word(Q,W).
                        
%   Check if a word is accepted (yes/no).
    start:- write('PushDown accepting EQUAL'),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).         

% intially the stack is empty. We put a special marker: c
    stack([c]).

% push something in your stack. Remove old stack and put new stack instead
    push(H):- stack(L),(atom(H) -> New=[H|L] ; append(H,L,New)),
                       retract(stack(_)),assert(stack(New)).
    
% pop something out of the stack. Do not care what
    pop:- stack([_|T]),retract(stack(_)),assert(stack(T)).

% 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|_]).
   
% check if stack is empty
    empty_stack:- stack([]).