CS 481 Automata, Winter 1998 
NFA (without-e) to DFA CONVERSION
CPROLOG SOURCE CODE
----------------------------------


symbol(X) :- delta(_,X,_).
alphabet(A) :- setof(X,symbol(X),A).
all_final_states(F) :- setof(X,final_state(X),F).
set_d([],X,[]).
set_d([Q|L],X,D) :- d(Q,X,P1), set_d(L,X,P2), union(P1,P2,D1), 
                    qsort(D1,D).
d(Q,A,S) :- setof(P,delta(Q,A,P),S),!.
d(Q,A,[]).

split(H,[A|X],[A|Y],Z) :- A @< H, split(H,X,Y,Z).
split(H,[A|X],Y,[A|Z]) :- A @> H, split(H,X,Y,Z).
split(_,[],[],[]).

qsort([],[]).
qsort([H|T],S) :-  split(H,T,A,B), qsort(A,A1), qsort(B,B1),
  append(A1,[H|B1],S).

member(X,[X|L]) :- !.
member(X,[Y|L]) :- member(X,L).
append([],L,L).
append([X|L],M,[X|N]) :- append(L,M,N).
union([],S,S).
union([X|L],S1,S) :- member(X,S1),!,union(L,S1,S).
union([X|L],S1,[X|S]) :- union(L,S1,S). 
intersect([],S,[]).
intersect([X|L],S1,[X|S]) :- member(X,S1),!,intersect(L,S1,S).
intersect([X|L],S1,S) :- intersect(L,S1,S). 

write_start(S) :- write(start_state), write('('), write([S]),
                  write(')'), write('.'), nl.
write_trans(Q,X,D) :- write(delta), write('('), write(Q), write(','), 
          write(X), write(','), write(D), write(')'), write('.'), nl.
write_final(Q) :- write(final_state), write('('), write(Q), write(')'),
                  write('.'), nl.

convert :- tell('out.dat'), start_state(S), write_start(S),
           Queue = [[S]], States = [[S]], alphabet(A), 
           expand(A,States,Queue,AllStates), 
           all_final_states(F), decide_final(AllStates,F), told.

expand(A,S,[],S) :- !.
expand(A,S,[Q|L],AllStates) :- process(A,Q,S,L,NewS,NewL),
                     expand(A,NewS,NewL,AllStates).

process([],Q,S,L,S,L).
process([X|B],Q,S,L,NewS,NewL) :- process_symbol(X,Q,S,To), 
    union(S,To,S1), append(L,To,L1), process(B,Q,S1,L1,NewS,NewL).


process_symbol(X,Q,S,[])  :- set_d(Q,X,D), member(D,S), write_trans(Q,X,D).
process_symbol(X,Q,S,[D]) :- set_d(Q,X,D), not member(D,S),
                             write_trans(Q,X,D).


decide_final([],F).
decide_final([Q|L],F) :- intersect(Q,F,G), G \== [], !,
                         write_final(Q), decide_final(L,F).
decide_final([Q|L],F) :- decide_final(L,F).