%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Patrick Blackburn, 1999.
% Kristina Striegnitz, 2002.
%
% This file contains the code for a simple fsa recognizer:
%
%   recognize2(+Node,?SymbolList)
%        
%        SymbolList:  list of words which you want to test.
%                 
%        Node:  number of the node you wish to start from
%
% This clause succeeds if SymbolList can be recognized by the fsa in the
% database starting from the node 'Node' and ending in a final state.
%
% This file furthermore defines:
% + two driver predicates test2(+SymbolList) (for recognition) and 
%                         generate2(-SymbolList) (for generation)
% + traverse2/3
%
% NOTE: traverse2 is an extension of traverse1 that can handle 
        jump arcs. Everything else is the same as with recognize1.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% recognize2(+Node,?List)

%%% base case
recognize2(Node,[]) :-
    final(Node).

%%% make a transition reading the first Symbol of the input 
%%% and call recognize2 recursively with the rest of the input
recognize2(Node_1,String) :-
    arc(Node_1,Node_2,Label),
    traverse2(Label,String,NewString),
    recognize2(Node_2,NewString).


%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% traverse2(+Label,?List, -List)
%%% a) if Label is '#' (jump arc!), the input list is returned unchanged
%%% b) if Label unifies with the first element of the List in
%%%    the second argument, the rest of this list is returned.
%%% otherwise, the predicate fails

traverse2('#',String,String).
traverse2(Label,[Label|Symbols],Symbols).


%%%%%%%%%%%%%%%%%%%%%%%%%
%%% two driver predicates

test2(Symbols) :-
    initial(Node),
    recognize2(Node,Symbols).

generate2(X) :-
   test2(X).