/* File: nfa0.pl     System: SWI-Prolog  5.2.8
   Author: MM
   Date: 10/14/2003
   Title: Check if a word is accepted by a NFA
   
   DFA accepts words that start with a.
   Alphabet={a,b}, States={0,1}   Favorable={2} start is state 0.
   Transition function is:
                t(0,a)=0    t(0,a)=1
                t(1,a)=1    t(1,b)=1     t(1,b)=2 
                   
        ?- start.
        A NFA that accepts a(a+b)*b 
        Input a word as a list(Ex: [a,b,b]) :[a,a,b,a,b].
        Path followed by NFA-reversed: 2b1a1b1a0a0
        
        Yes
        7 ?- start.
        A NFA that accepts a(a+b)*b 
        Input a word as a list(Ex: [a,b,b]) :[a,a,a,b,b,b,a].
        Path followed by NFA-reversed: 
        No
*************************************************/
% This is the definition of our NFA in Prolog.

    t(0,a,0).   t(0,a,1).   
    t(1,a,1).   t(1,b,1).   t(1,b,2).  
    
    start(0).       % 0 is the starting state
    
    favorable(2). % 1 is a favorable state
       
%   Check if a word is accepted.
   
    check_word(S,[]):- favorable(S),write(S).
    check_word(S,[H|T]) :- t(S,H,Q),check_word(Q,T),write(H),write(S).

%    See if a word is accepted, if yes print path.

    start:- write('A NFA that accepts a(a+b)*b \n'),
        write('Input a word as a list(Ex: [a,b,b]) :'),
        read(W),write('Path followed by NFA-reversed: '),        
        start(S),check_word(S,W).