/********************************************
   File: pda3.pl     System: SWI-Prolog  5.2.8
   Author: Mihaela Malita
   Date: 11/8/2003
   Title:  Check if a PDA is NPDA
           Deterministic PushDown Automata (DPDA) versus 
           NonDeterministic Pushdown Automata (NDPA)
           NPDA =/= DPDA   
          
          ?- npda.
          t- (s, b, a)- (f, e)-t- (s, b, [a, b])- (f, b)
          Yes
***********************************************/
t((s0,a,e),(s,a)).   
t((s,a,e),(s,a)).    
t((s,b,a),(f,e)).  
t((s,b,[a,b]),(f,b)).   % add this to have a compatible pair 
t((q,e,e),(s0,e)).      % JUMP
t((f,b,a),(f,e)).    
start(q).  favorable(f).
/*************** prefix(Prefix,Word_as_List) *************
?- prefix([m,a],[m,a,r,y]).
?- prefix(m,[m,a,r,y]).
?- prefix([m,a,r,y],[m,a,r,y]).
All are yes
*/
prefix(P,W):- atom(P)-> (P=W ;W=[P|_]); append(P,_,W).

/* Check if a given PDA has jumps (like: t((State1,e,e),(State2,e)). )
?- has_jumps.
yes
*/
has_jumps:- t((_,e,e),(_,e)).
/**********************************************************
Definition. Two transitions in a PDA 
((s1,a1,top0),((_,_)) and ((s2,a2,top2),(_,_)) are compatible if:
1) s1=s2
2) a1=a2 or a=e or a2=e
and
3) either top0 is prefix of top2 or top2 is prefix of top0.
Example: ?- compatible(t((s0,a,c),(q,a)),t((s0,a,c),(q,e))).
?- compatible(t((s0,a,[c,c]),(q,a)),t((s0,a,c),(q1,e))).
?- compatible(t((s0,a,c),(q,a)),t((s0,a,[c,a]),(q1,e))).
?- compatible(t((s0,e,c),(q,a)),t((s0,a,c),(q1,e))).
?- compatible(t((s0,a,[c,d]),(q,a)),t((s0,e,c),(q1,e))).
all are YES 
*********************************************************/
compatible(t((S1,A,Top0),_),t((S2,B,Top2),_)):- 
                    S1=S2,
                    (A=B ; A=e ; B=e),
                    (prefix(Top0,Top2);prefix(Top2,Top0)).

% There is at least one pair of compatible transactions
compatible_transitions:-
    t(X0,Y0),t(X1,Y1),not(t(X0,X1),t(Y0,Y1)),
    compatible(t(X0,Y0),t(X1,Y1)) -> write(t-X0-Y0-t-X1-Y1). % prints the compatible ones
             
/*******************************************************
* Definition. A PDA is called DETERMINISTIC (DPDA) if it has no distinct compatible transitions and 
no JUMP transitions: ((s,e,e,),(q,e)).
So let's define npda/0 - 
it is nondeterministic if there is at least one compatible transaction 
or it has a jump.
*/
npda:- compatible_transitions;
       has_jumps.