% Finite state transducer. 
% with epsilon-transitions.

fst(TapeInput,TapeOutput):-
	initial_fst(S),
	fst(TapeInput,S,TapeOutput).

fst([],S,[]):- 
	final_fst(S).

fst(Input,S,Output):-
	trans_tab_fst(S,In,Out,NS),
	append(In,Input_new,Input),
	append(Out,Output_new,Output),
%	write('Zustand '), write(S), nl,
%	write('Leseband '), write(Input), nl,
%	write('schreibt '), write(Out), nl, nl,
	fst(Input_new,NS,Output_new).


% append(L1,L2,L3)
% L3 is the concatenation of L1 and L2

append([],L,L).
	
append([H|T1],L,[H|T2]):-
	append(T1,L,T2).


% member(E,L)
% E is member of list L

member(E,[E|L]).

member(E,[H|L]):- 	
	member(E,L).

% FST transition table:
% trans_tab/4
% trans_tab(State, Input, Output, New State)

trans_tab_fst(0,['^'],[],0).
trans_tab_fst(0,['#'],['#'],0).
trans_tab_fst(0,[X],[X],0):- other(X).
trans_tab_fst(0,[z],[z],1).	
trans_tab_fst(0,[s],[s],1).	
trans_tab_fst(0,[x],[x],1).	

trans_tab_fst(1,[z],[z],1).	
trans_tab_fst(1,[s],[s],1).	
trans_tab_fst(1,[x],[x],1).	
trans_tab_fst(1,['^'],[],2).
trans_tab_fst(1,['#'],['#'],0).	
trans_tab_fst(1,[X],[X],0):- other(X).

trans_tab_fst(2,[z],[z],1).
trans_tab_fst(2,[x],[x],1).
trans_tab_fst(2,[s],[s],5).
trans_tab_fst(2,[],[e],3).
trans_tab_fst(2,[X],[X],0):- other(X).

trans_tab_fst(3,[s],[s],4).

trans_tab_fst(4,['#'],['#'],0).

trans_tab_fst(5,['^'],[],2).
trans_tab_fst(5,[s],[s],1).
trans_tab_fst(5,[x],[x],1).
trans_tab_fst(5,[z],[z],1).
trans_tab_fst(5,[X],[X],0):- other(X).

initial_fst(0).
final_fst(0).
final_fst(1).
final_fst(2).


alpha([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]).

other(X):-
	alpha(AL),
	member(X,AL),
	X \= z,
	X \= s, 	
	X \= x. 