%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Patrick Blackburn, 1999.
% Kristina Striegnitz, 2002.
%
% This file contains the code for a finite state transducer
% with two tapes that can handle jump arcs. The code is the
% same as for trans1.pl except for the traverse predicate.
%
% Usage: testtrans2(?List,?List)
%        The Lists represent the two tapes.
%
% Main predicate: transduce2(+Node,?SymbolList,?SymbolList)
%                 SymbolList:  the two tapes
%                 Node:  number of the node you wish to start from
%
% This file furthermore defines:
% + the driver predicate testtrans2(?SymbolList,?SymbolList)
% + traverse2/5
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% transduce1(+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
transduce2(Node,[],[]) :-
    final(Node).

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% traverse1(+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
traverse2('#':'#',String_left,String_left,
                    String_right,String_right).

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

% The right tape has a jump symbol
traverse2(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
traverse2(Sym_left:Sym_right,[Sym_left|Rest_left],Rest_left,
                               [Sym_right|Rest_right],Rest_right).


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

testtrans2(Left,Right) :-
    initial(Node),
    transduce2(Node,Left,Right).