%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Patrick Blackburn, 1999.
% Kristina Striegnitz, 2002.
% Aljoscha Burchardt, 2003.
%
% This file contains the code for a finite state transducer
% with two tapes that can handle jump arcs.
%
% Usage: testtrans(+FSA,?List,?List)
%        +FSA is the automaton to be used,
%        the Lists represent the two tapes.
%
% Main predicate: transduce(+FSA,+Node,?SymbolList,?SymbolList)
%                 +FSA: the automaton to be used
%                 SymbolList:  the two tapes
%                 Node:  number of the node you wish to start from
%
% This file furthermore defines:
% + traverse/5
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% transduce(A,+Node,?List,?List)
%%% Simulates the steps of the transducer. Evaluates to true, iff a
%%% final state is reached when both tapes have been read completely.

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

% the recursive clause: the transducer makes one step and then
% the predicate is called recursively with the rest of the tapes.
transduce(A,Node_1,String_left,String_right) :-
    trans(A,Node_1,Node_2,Label),
    traverse(Label,String_left,NewString_left,String_right,NewString_right),
    transduce(A,Node_2,NewString_left,NewString_right).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% traverse(+Symbol:Symbol,+List,-List,+List,-List)
%%% Tests whether the two symbold provided by the first argument
%%% either indicate a jump ('#') or else match with the first 
%%% elements in the input lists (args 2 and 4).

% Both tapes have a jump symbol
traverse('#':'#',String_left,String_left,
                    String_right,String_right).

% The left tape has a jump symbol
traverse('#':Sym_right,String_left,String_left,
                           [Sym_right|Rest_right],Rest_right).

% The right tape has a jump symbol
traverse(Sym_left:'#',[Sym_left|Rest_left],Rest_left,
                           String_right,String_right).

% Neither  tape has a jump symbol. This is
% just the definition of traverse used in trans1.pl
traverse(Sym_left:Sym_right,[Sym_left|Rest_left],Rest_left,
                               [Sym_right|Rest_right],Rest_right).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% the driver predicate

testtrans(A,Left,Right) :-
    start(A,Node),
    transduce(A,Node,Left,Right).
