%Avtomat: [broi systoqniq,na4alni systoqniq,kraini systoqnia,funkciq na prehodite]

%Avtomat razpoznava6t praznata duma
empty([1,[0],[0],[]]).

%Avtomat razpoznava6 edna bukva
single(A,[2,[0],[1],[[0,A,1]]]).

%shift(N,L,R).
shift(N,[],[]).
shift(N,[H|T],[B|C]):-B is N+H,shift(N,T,C).

shift3(N,[],[]).
shift3(N,[[Q1,A,Q2]|T],[[P1,A,P2]|C]):-P1 is Q1+N,P2 is Q2+N,shift3(N,T,C).

shiftAll([N1,S1,F1,D1],[N2,S2,F2,D2],[N2,S,F,D]):-shift(N1,S2,S),shift(N1,F2,F),shift3(N1,D2,D).

union([N1,S1,F1,D1],B,[N,S,F,D]):-shiftAll([N1,S1,F1,D1],B,[N2,S2,F2,D2]),N is N1+N2,append(S1,S2,S),append(F1,F2,F),append(D1,D2,D).

%clone(Q,A,S,R)
clone(Q,A,[],[]).
clone(Q,A,[S|T],[[Q,A,S]|NT]):-clone(Q,A,T,NT).

%findAll(F1,D1,S2,D).
findAll(F1,[],S2,[]).
findAll(F1,[[Q1,A,Q2]|T],S2,D):-member(Q2,F1),clone(Q1,A,S2,R),findAll(F1,T,S2,X),append(R,X,D).
findAll(F1,[[Q1,A,Q2]|T],S2,D):-not(member(Q2,F1)),findAll(F1,T,S2,D).

findStart(F1,S1,S2,S1):-not(member(X,F1),member(X,S1)).
findStart(F1,S1,S2,S):-member(X,F1),member(X,S1),append(S1,S2,S).

concat([N1,S1,F1,D1],B,[N,S,F2,D]):-shiftAll([N1,S1,F1,D1],B,[N2,S2,F2,D2]),N is N1+N2,findStart(F1,S1,S2,S),findAll(F1,D1,S2,D3),append(D1,D2,D4),append(D3,D4,D).

plus([N,S,F,D],[N,S,F,D1]):-findAll(F,D,S,X),append(d,X,D1).
star(A,S):-plus(A,P),empty(E),union(E,P,S).