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


symbol(X) :- delta(_,X,_), X \== nil.
alphabet(A) :- setof(X,symbol(X),A).
all_final_states(F) :- setof(X,final_state(X),F).
state(S) :- delta(S,_,_).
state(S) :- delta(_,_,S).
all_states(S) :- setof(X,state(X),S1), setof(X,state(X),S2),
                 union(S1,S2,S).
member(X,[X|L]) :- !.
member(X,[Y|L]) :- member(X,L).
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). 
e_path(Q,Q).
e_path(Q,R) :- delta(Q,nil,R).
e_path(Q,R) :- delta(Q,nil,P), e_path(P,R).
e_closure(Q,C) :- setof(R,e_path(Q,R),C).
set_e_closure([],[]).
set_e_closure([Q|L],D) :- e_closure(Q,C), set_e_closure(L,M),
                          union(C,M,D).
set_d([],X,[]).
set_d([Q|L],X,D) :- d(Q,X,P1), set_d(L,X,P2), union(P1,P2,D).
d(Q,A,S) :- setof(P,delta(Q,A,P),S),!.
d(Q,A,[]).
rm_etrans :- tell('out.dat'),alphabet(A),print_start,all_states(S),
             process(A,S),decide_final(S), told.
print_start :- start_state(S), write(start_state), write('('), write(S),
               write(')'), write('.'),nl. 
process(A,[]).
process(A,[Q|L]) :- process_state(A,Q), process(A,L).
process_state([],Q).
process_state([X|L],Q) :- e_closure(Q,C), set_d(C,X,D),
              set_e_closure(D,P), output(Q,X,P), process_state(L,Q).
output(Q,X,[]).
output(Q,X,[P|L]) :- write(delta),write('('),write(Q),write(','),
                     write(X), write(','), write(P), write(')'),
                     write('.'), nl, output(Q,X,L).
decide_final([]).
decide_final([Q|L]) :- e_closure(Q,C), all_final_states(F),
                       intersect(C,F,S), S \== [], !, write(final_state),
                       write('('), write(Q), write(')'), write('.'), nl,
                       decide_final(L).
decide_final([Q|L]) :- decide_final(L).