/********************************************
   File: pda2.pl     System: SWI-Prolog  5.2.8
   Author: Mihaela Malita
   Date: 11/8/2003
   Title:  A Pushdown Automaton(PDA) for Even Length Palindromes
   Grammar is:
   {S-> aSa, S-> bSb, S -> e }
   Alphabet={a,b} States={s,f} Favorable={f} Start_state=s Gamma={e,a,b,S}
        ?- start.
        PDA accepting Even Length Palindromes
        Input your word: [a,b,a,b,b,a,b,a].
        s-e-e-f-s  stack-[s]
        f-e-s-f-e  stack-[]         % bad! look back
        f-e-s-f-[a, s, a]  stack-[a, s, a]
        f-e-a-f-e  stack-[s, a]
        f-e-s-f-e  stack-[a]         % bad! look back
        f-e-s-f-[a, s, a]  stack-[a, s, a, a]   % bad! look back
        f-e-s-f-[b, s, b]  stack-[b, s, b, a]
        f-e-b-f-e  stack-[s, b, a]
        f-e-s-f-e  stack-[b, a]         % bad! look back
        f-e-s-f-[a, s, a]  stack-[a, s, a, b, a]
        f-e-a-f-e  stack-[s, a, b, a]
        f-e-s-f-e  stack-[a, b, a]     % bad! look back
        f-e-s-f-[a, s, a]  stack-[a, s, a, a, b, a] % bad look back
        f-e-s-f-[b, s, b]  stack-[b, s, b, a, b, a]
        f-e-b-f-e  stack-[s, b, a, b, a]
        f-e-s-f-e  stack-[b, a, b, a]
        f-e-b-f-e  stack-[a, b, a]
        f-e-a-f-e  stack-[b, a]
        f-e-b-f-e  stack-[a]
        f-e-a-f-e  stack-[]
      
        Yes
***********************************************/
% Definition for PDA starting from the grammar
    t((s,e,e),(f,s)).       % jump 
    t((f,e,s),(f,[a,s,a])). % push
    t((f,e,s),(f,[b,s,b])). % push
    t((f,e,s),(f,e)).       % pop
    t((f,a,a),(f,e)).       % pop
    t((f,b,b),(f,e)).       % pop
    
    start(s).           
    favorable(f).

%  Accepted if: Word is finished, Stack is empty, Automaton is in favorable state
    check_word(Q,[],[]):- favorable(S).

%   t((s,e,e),(f,s)).       % push 
    check_word(Q,W,Stack):- t((Q,e,e),(F,Top)),NewStack=[Top|Stack],
                            write(Q-e-e-F-Top),tab(2),write(stack-NewStack),nl,nl,
                            check_word(F,W,NewStack).    

%  t((f,e,s),(f,e)).       % pop
    check_word(Q,W,[Top|Rest]):- t((Q,e,Top),(F,e)),
                                write(Q-e-Top-F-e),tab(2),write(stack-Rest),nl,
                                check_word(F,W,Rest).
                        
%  t((f,e,s),(f,[a,s,a])).  %push
    check_word(Q,W,[Top|Rest]):- t((Q,e,Top),(F,NewTop)),
                                replace(NewTop,Rest,Stack),
                                write(Q-e-Top-F-NewTop),tab(2),write(stack-Stack),nl,
                                check_word(F,W,Stack).
                        
%  t((f,a,a),(f,e)).       % pop
    check_word(Q,[H|T],[Top|Rest]):- t((Q,H,Top),(F,e)),
                                    write(Q-e-Top-F-e),tab(2),write(stack-Rest),nl,
                                    check_word(F,T,Rest).

%   Check if a word is accepted (yes/no).
    start:- write('PDA accepting Even Length Palindromes'),nl,
            write('Input your word: '),read(W),
            start(S),check_word(S,W,[]).

% Ex: replace([a,b],[s,a,a],[a,b,s,a,a]). put something new on top of the stack
replace(NewTop,Rest,NewStack):- atom(NewTop) -> NewStack=[NewTop|Rest]; 
                                append(NewTop,Rest,NewStack).