re(soheil, 

cat( star(or(a,b)), cat( a, cat( or(a,b), cat( or(a,b), #))))

).

re(0, cat(star(or(a,b)),cat(a,cat(or(a,b),#)))).
re(1, cat(cat(cat(cat(star(or([a,1],[b,2])),[a,3]),[b,4]),[b,5]),[#,6])).
re(2, cat(cat(cat(star(or([a,1],[b,2])),[a,3]),[b,4]),[b,5])).
re(3, cat(cat(star(or([a,1],[b,2])),[a,3]),[b,4])).
re(4, cat(star(or([a,1],[b,2])),[a,3])).
re(5, star(or([a,1],[b,2]))).
re(6, or([a,1],[b,2])).
re(7, [a,1]).
re(8, [#,6]).
re(9, cat(or(star(or(cat(b,a),b)),star(or(cat(b,b),a))),#)).
re(10, cat(or(cat(star(cat(a,b)),star(cat(b,a))),cat(a,star(a))),#)).
%
nullable([nil,_]).
nullable(or(R,_)) :- nullable(R).
nullable(or(_,S)) :- nullable(S).
nullable(cat(R,S)) :- nullable(R), nullable(S).
nullable(star(_)).
%
firstpos([nil,_],[]).
firstpos([_,N],[N]) :- N>0.
firstpos(or(R,S),P) :- 
  firstpos(R,P1), firstpos(S,P2), union(P1,P2,P).
firstpos(cat(R,S),P) :- 
  nullable(R), firstpos(R,P1), firstpos(S,P2), union(P1,P2,P).
firstpos(cat(R,_),P) :- 
  \+ nullable(R), firstpos(R,P).
firstpos(star(R),P) :- 
  firstpos(R,P).
%
lastpos([nil,_],[]).
lastpos([_,N],[N]) :- N>0.
lastpos(or(R,S),P) :- 
  lastpos(R,P1), lastpos(S,P2), union(P1,P2,P).
lastpos(cat(R,S),P) :- 
  nullable(S), lastpos(R,P1), lastpos(S,P2), union(P1,P2,P).
lastpos(cat(_,S),P) :- 
  \+ nullable(S), lastpos(S,P).
lastpos(star(R),P) :- 
  lastpos(R,P).
%
extractNodes([_,_],[]).
extractNodes(star(R),[star(R)|L]) :- 
  extractNodes(R,L).
extractNodes(cat(R,S),[cat(R,S)|L]) :- 
  extractNodes(R,L1), extractNodes(S,L2), append(L1,L2,L).
extractNodes(or(R,S),L) :- 
  extractNodes(R,L1), extractNodes(S,L2), append(L1,L2,L).
%
followpos(R,I,P) :- extractNodes(R,N), setof(J,fpos(N,I,J),P).
followpos(R,I,[]) :- extractNodes(R,N), \+ setof(J,fpos(N,I,J),_).
fpos(N,I,J) :- 
  member(cat(R,S),N), lastpos(R,L), member(I,L), 
  firstpos(S,M), member(J,M).
fpos(N,I,J) :- 
  member(star(R),N), lastpos(R,L), member(I,L), 
  firstpos(star(R),M), member(J,M).
%
assignNumber(N,A,[A,N],M) :- atomic(A), M is N+1.
assignNumber(N,star(R),star(T),M) :- assignNumber(N,R,T,M).
assignNumber(N,or(R,S),or(T1,T2),M) :- 
  assignNumber(N,R,T1,N1), 
  assignNumber(N1,S,T2,M).
assignNumber(N,cat(R,S),cat(T1,T2),M) :- 
  assignNumber(N,R,T1,N1), 
  assignNumber(N1,S,T2,M).
%%
corresponds(P,A,[A,P]).
corresponds(P,A,star(R)) :- corresponds(P,A,R).
corresponds(P,A,cat(R,_)) :- corresponds(P,A,R).
corresponds(P,A,cat(_,S)) :- corresponds(P,A,S).
corresponds(P,A,or(R,_)) :- corresponds(P,A,R).
corresponds(P,A,or(_,S)) :- corresponds(P,A,S).
%
findU(_,_,[],U,V) :- sort(U,V).
findU(A,R,[P|T],U,Ufinal) :-
  corresponds(P,A,R), followpos(R,P,FP), union(U,FP,V), findU(A,R,T,V,Ufinal).
findU(A,R,[P|T],U,Ufinal) :-
  \+ corresponds(P,A,R), findU(A,R,T,U,Ufinal).
%
processState([],_,_,OldUnmarked,_,OldUnmarked).
processState([A|B],R,S,OldUnmarked,Marked,NewUnmarked) :-
  findU(A,R,S,[],U), 
  union(OldUnmarked,Marked,AllStates),
  \+ member(U,AllStates),
  append(OldUnmarked,[U],TempUnmarked),
  write('delta('),write(S),write(','),write(A),write(','),write(U),write(')'), nl,
  processState(B,R,S,TempUnmarked,Marked,NewUnmarked).
processState([A|B],R,S,OldUnmarked,Marked,NewUnmarked) :-
  findU(A,R,S,[],U), 
  union(OldUnmarked,Marked,AllStates),
  member(U,AllStates),
  write('delta('),write(S),write(','),write(A),write(','),write(U),write(')'), nl,
  processState(B,R,S,OldUnmarked,Marked,NewUnmarked).
%%
printTransitions(_,_,[],M,M).
printTransitions(A,R,[S|L],M,Mfinal) :-
  processState(A,R,S,L,[S|M],NewL),
  printTransitions(A,R,NewL,[S|M],Mfinal).
%
getHashPos([#,P],P).
getHashPos(star(R),P) :- getHashPos(R,P).
getHashPos(cat(R,_),P) :- getHashPos(R,P).
getHashPos(cat(_,S),P) :- getHashPos(S,P).
getHashPos(or(R,_),P) :- getHashPos(R,P).
getHashPos(or(_,S),P) :- getHashPos(S,P).
%
finalStates(_,[]).
finalStates(R,[S|L]) :-
  getHashPos(R,Pos),
  member(Pos,S),
  write('final_state('), write(S), write(')'), nl,
  finalStates(R,L).
finalStates(R,[S|L]) :-
  getHashPos(R,Pos),
  \+ member(Pos,S),
  finalStates(R,L).
%
% A: Alphabet e.g. [a,b]
% R: regular expression
% e.g. R = cat(cat(cat(cat(star(or(a,b)),a),b),b),#)
% Rnum = cat(cat(cat(cat(star(or([a,1],[b,2])),[a,3]),[b,4]),[b,5]),[#,6])
%
re2dfa(A,R) :-
  assignNumber(1,R,Rnum,_),
  firstpos(Rnum,F), sort(F,G),
  write('start_state('), write(G), write(')'), nl,
  printTransitions(A,Rnum,[G],[],AllStates),
  sort(AllStates,States),
  finalStates(Rnum,States).
