%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Patrick Blackburn, 1999.
% Kristina Striegnitz, 2002.
% Stephan Walter, 2003
%
% This file contains the code for a simple fsa recognizer:
%
%   recognize(+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.
%
% The program is based on the Gazdar and Mellish program
% fstnrecg.pl. 
%
% This file furthermore defines:
% + two driver predicates test(+A(utomaton),+SymbolList) (for recognition) and 
%                         generate1(+A(utomaton),-SymbolList) (for generation)
% + traverse/3
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% recognize(+A,+Node,?List)

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

%%% make a transition reading the first Symbol of the input 
%%% and call recognize1 recursively with the rest of the input
recognize(A,Node_1,String) :-
    trans(A,Node_1,Node_2,Label),
    traverse(Label,String,NewString),
    recognize(A,Node_2,NewString).


%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% traverse(+Label,?List, -List)
%%% Evaluates to true if Label is the first element of the List in
%%% the second argument, and returns the rest of this list in its
%%% third argument.

traverse(Label,[Label|Symbols],Symbols).

%%% Add-on for jump arcs: Traverse jump arcs without doing anything.
traverse('#',Symbols,Symbols).

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

test(A,Symbols) :-
    start(A,Node),
    recognize(A,Node,Symbols).

generate(A,X) :-
   test(A,X).
