% endlicher Automat A = (Initial,Transitionen,Final)  HL,20.12.12
% Zustande: Zahlen
% Transition: (i,a,j)  fuer i -a-> j, Buchstabe a: atom

automat(aut(Init,Trans,Final)) :-
    transitions(Trans),
    numbers(Init),
    numbers(Final).

numbers([]).
numbers([N|Ns]) :-
    number(N),
    numbers(Ns).

transitions([]).
transitions([(I,A,J)|Ts]) :-
    transition((I,A,J)),
    transitions(Ts).

transition((I,A,J)) :-
    number(I), 
    number(J), 
    atom(A).

%

aut0(aut([0],[(0,a,1),(0,b,2),(0,a,3),
              (2,a,4),(3,b,1),(1,a,2)],[3,4])).
aut1(aut([0],[(0,b,1),(1,a,0),(0,b,3)],[3])).

% read_word(+Automat,+I,+Atoms,-J).

% reads(+Automat,+Atoms)
reads(Automat,Atoms) :-
    Automat = aut(Init,Trans,Final),
    member(I,Init), % waehle einen Anf.zustand
    read_word(Trans,I,Atoms,J),
    member(J,Final).

% read_word(+Trans,?I,+Atoms,?J)

read_word(Trans,I,[A|As],J) :-
    member((I,A,K),Trans),
    read_word(Trans,K,As,J).
read_word(_Trans,I,[],I).
    
% Vereinigung von A1 und A2:

% Falls A1 und A2 keinen gemeinsamen Zustand haben:
% einfach die Anfangs-, die End- und die Trans-Listen
% vereinigen:

% union_disj(+Automat1,+Automat2,-Automat)

union_disj(A1,A2,A) :-
    A1 = aut(Init1,Trans1,Fin1),
    A2 = aut(Init2,Trans2,Fin2),
    append(Init1,Init2,Init),
    append(Fin1,Fin2,Fin),
    append(Trans1,Trans2,Trans),
    A = aut(Init,Trans,Fin).

% Allgemein:
% 1. Berechne die maximale Zustandsnummer Max in A1
% 2. Mache eine Kopie A2Copy von A2, wo Zustandsnummern
%    I durch I+Max+1 ersetzt sind
% 3. benutze union_disj(A1,A2Copy,A)

maxstate(Automat,Max) :-
    maxstate(Automat,0,Max). % 0 = leerer Akkumulator

maxstate(aut(Init,Trans,Fin),Acc,Max) :-
    !,
    maxstate(Init,Acc,AccI),
    maxstate(Fin, AccI,AccF),
    maxstate(Trans,AccF,Max).

maxstate([(I,_A,J)|Trans],Acc,Max) :-
    !,
    K is max(I,J),
    M is max(Acc,K),
    maxstate(Trans,M,Max).

maxstate([I|Is],Acc,Max) :-
    number(I),
    K is max(I,Acc),
    maxstate(Is,K,Max).

maxstate([],Acc,Acc).
    
copy(aut(Init,Trans,Fin),Max,aut(InitM,TransM,FinM)) :-
    !,
    copy(Init,Max,InitM),
    copy(Fin,Max,FinM),
    copy(Trans,Max,TransM).

copy([(I,A,J)|Trans],Max,[(IM,A,JM)|TransM]) :-
    !,
    copy(I,Max,IM),
    copy(J,Max,JM),
    copy(Trans,Max,TransM).

copy([I|Is],Max,[IM|IsM]) :-
    !, copy(I,Max,IM),
    copy(Is,Max,IsM).

copy([],_Max,[]) :- !.

copy(I,Max,IM) :-
    IM is I+Max+1.


% Allgemeiner Fall: 

union(Automat1,Automat2,Automat) :-
    maxstate(Automat1,M),
    copy(Automat2,M,Automat2Copy),
    union_disj(Automat1,Automat2Copy,Automat).

