/****************************************************************
Operations on FSAs: union, intersection, copying


Original implementation: 
Fistame system by Ralph Debusmann, Revision date 04/02/99

Based on ideas from a course by Ronald M. Kaplan and Martin Kay:
Finite-State Methods in Natural-Language Processing: Algorithms

This version: 20/05/03 stwa
****************************************************************/

:- multifile start/2,trans/4,final/2.

:- dynamic start/2,trans/4,final/2.


%% General framework

% The main predicate, backbone for most of the code

scan(A):-
  retractall(state(A,_)),       % retract state markers
  start(A,S),                   % find start state
  scan_state(A,S).              % start scanning from there

scan_state(A,S):-
  state(A,S),!.                 % state already scanned?

scan_state(A,S):-
  assert(state(A,S)),           % mark state as scanned
  check_final(A,S),             % process final states
  (  setof(D,X^trans(A,S,D,X),Ds)
  -> scan_states(A,Ds)          % scan states reachable from current one
  ;  true                       
  ).


check_final(A,S):-
  final(A,S),!.                 % final states receive special treatment

check_final(_,_).               % non-final states: no processing necessary - just return true



scan_states(A,[S|Ss]):-
  scan_state(A,S),              % scan state from state list
  scan_states(A,Ss).            % go to next state from state list

scan_states(_,[]).              % state list already emptied?







%% Code for operations

% Copy automata (binary)

start(cp(A1,A2),S):-
  start(A1,S),
  retractall(start(A2,_)),
  retractall(trans(A2,_,_,_)),
  retractall(final(A2,_)),
  assert(start(A2,S)).

trans(cp(A1,A2),S,D,X):-
  trans(A1,S,D,X),
  assert(trans(A2,S,D,X)).

final(cp(A1,A2),S):-
  final(A1,S),
  assert(final(A2,S)).

% Intersect automata

start((A1,A2),S1/S2):-
  start(A1,S1),
  start(A2,S2).

trans((A1,A2),S1/S2,D1/D2,X):-
  trans(A1,S1,D1,X),
  trans(A2,S2,D2,X).

final((A1,A2),S1/S2):-
  final(A1,S1),
  final(A2,S2).

% Produce the union of automata

start((_;_),start).

trans((A1;_),start,1/S1,'#'):-
  start(A1,S1).

trans((_;A2),start,2/S2,'#'):-
  start(A2,S2).

trans((A1;_),1/S1,1/D1,X):-
  trans(A1,S1,D1,X).

trans((_;A2),2/S2,2/D2,X):-
  trans(A2,S2,D2,X).


final((A1;_),1/S1):-
  final(A1,S1).

final((_;A2),2/S2):-
  final(A2,S2).

% Print an automaton

start(pr(A),S):-
  start(A,S),
  format("~nautomaton ~w:~n~ninitial state ~w~n~n",[A,S]).

trans(pr(A),S,X,D):-
  trans(A,S,X,D),
  format("from ~w over ~w to ~w~n",[S,X,D]).

final(pr(A),S):-
  final(A,S),
  format("~nfinal state ~w~n",[S]).

% Invert an automaton

start(comp(A),S):-
  start(A,S).
  
trans(comp(A),S,X,D):-
  trans(A,S,X,D).
  
final(comp(A),S):-
  \+final(A,S).
