%% Ein einfacher Transducer für
%% s:0 <=> {s:s, x:x, z:z} +:0 _

%% Wegen der Epsilon-Paare, läuft der Transducer nur
%% - als Recognizer   z.B.: transduce([r,a,s,'+',s,t], [r,a,s,t]).
%% - und als Vorwärtübersetzer   z.B.: transduce([r,a,s,'+',s,t], X).
%%
%% Bei Rückwärtsübersetzungen arbeitet er nicht immer korrekt.
%% z.B.: transduce(X, [r,e,n,n,s,t]).

%% (c)  Martin Volk

:- use_module(library(lists)).


initial(1).
final(4).
final(1).

%% von Knoten 1
arc(1,2, [s,s]).
arc(1,2, [z,z]).
arc(1,2, [x,x]).
arc(1,1, [X, X]) :-
  %% alle Zeichen ausser s,x,z,eps,'+'
  member(X, [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,t,u,v,w,y]).
arc(1,1, ['+', eps]).

%% von Knoten 2
arc(2,3, ['+', eps]).
arc(2,1, [X, X]) :-
  %% alle Zeichen ausser '+'
  member(X, [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,eps]).

%% von Knoten 3
arc(3,4, [s, eps]).

%% von Knoten 4
arc(4,4, [X, X]) :-
  %% alle Zeichen ausser 'eps'
  member(X, [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,'+']).


transduce(String1, String2) :-
  initial(Node),
  transduce_aux(Node, String1, String2),
  !.

transduce_aux(Node, [], []) :-
  final(Node).

transduce_aux(FromNode, String1, String2) :-
  arc(FromNode, ToNode, Label),
  traverse(Label, String1, NewString1, String2, NewString2),
  transduce_aux(ToNode, NewString1, NewString2).


%% Vorschriften zur Traversierung von Epsilon-Kanten
traverse([X, eps], [X|RestS1], RestS1, String2, String2) :-
  !.
traverse([eps, Y], String1, String1, [Y|RestS2], RestS2) :-
  !.
traverse([X, Y], [X|RestS1], RestS1, [Y|RestS2], RestS2).


/* *************** Beispiele *********************
%% als Recognizer
| ?- transduce([m,i,x,'+',s,t,e], [m,i,x,t,e]).
yes

| ?- transduce([m,i,x,'+',s,t,e], [m,i,x,s,t,e]).
no

%% vorwärts
| ?- transduce([r,a,s,'+',s,t,e], X).
X = [r,a,s,t,e]

| ?- transduce([m,i,x,'+',s,t,e], X).
X = [m,i,x,t,e]

| ?- transduce([r,e,n,n,'+',s,t], X).
X = [r,e,n,n,s,t]

%% rückwärts
| ?-  transduce(X, [r,a,s,t]).
X = [r,a,s,+,s,t] 

| ?- transduce(X, [r,e,n,n,s,t]).
X = [r,e,n,n,s,+,s,t]  %% Fehler!


************************************************** */