Solve the following problems from the textbook:

    2.5 (b), (c) -- Also minimize the DFAs
    2.6
    3.3 (c) -- Also verify that it is not ambiguous by running it through
               JCup
    3.5
    3.6

Prolog Programs for

1. (rmet.pl) Removing Empty Transitions
2. (ntd.pl) NFA (without empty transitions) to DFA conversion
3. (min.pl) Minimizing DFA

Sample Run:

[~/public_html/4340/f04][1:44pm] more m1.pl
start_state(q1).
final_state(q7).
delta(q1,nil,q2).
delta(q1,x,q5).
delta(q2,nil,q3).
delta(q2,y,q6).
delta(q3,nil,q4).
delta(q4,nil,q1).
delta(q5,nil,q6).
delta(q5,z,q2).
delta(q6,nil,q7).
[~/public_html/4340/f04][1:45pm] pl
Welcome to SWI-Prolog (Version 3.2.9)
Copyright (c) 1993-1999 University of Amsterdam.  All rights reserved.

For help, use ?- help(Topic). or ?- apropos(Word).

?- ['rmet.pl'].
rmet.pl compiled, 0.01 sec, 6,816 bytes.

Yes
?- ['m1.pl'].
m1.pl compiled, 0.01 sec, 1,212 bytes.

Yes
?- rm_etrans.

Yes
?- halt.
[~/public_html/4340/f04][1:45pm] more out.dat
start_state(q1).
delta(q1,x,q5).
delta(q1,x,q6).
delta(q1,x,q7).
delta(q1,y,q6).
delta(q1,y,q7).
delta(q2,x,q5).
delta(q2,x,q6).
delta(q2,x,q7).
delta(q2,y,q6).
delta(q2,y,q7).
delta(q3,x,q5).
delta(q3,x,q6).
delta(q3,x,q7).
delta(q3,y,q6).
delta(q3,y,q7).
delta(q4,x,q5).
delta(q4,x,q6).
delta(q4,x,q7).
delta(q4,y,q6).
delta(q4,y,q7).
delta(q5,z,q1).
delta(q5,z,q2).
delta(q5,z,q3).
delta(q5,z,q4).
final_state(q5).
final_state(q6).
final_state(q7).
[~/public_html/4340/f04][1:45pm] mv out.dat m2.pl
[~/public_html/4340/f04][1:45pm] pl
Welcome to SWI-Prolog (Version 3.2.9)
Copyright (c) 1993-1999 University of Amsterdam.  All rights reserved.

For help, use ?- help(Topic). or ?- apropos(Word).

?- ['ntd.pl'].
ntd.pl compiled, 0.00 sec, 7,328 bytes.

Yes
?- ['m2.pl'].
m2.pl compiled, 0.00 sec, 2,268 bytes.

Yes
?- convert.

Yes
?- halt.
[~/public_html/4340/f04][1:46pm] more out.dat
start_state([q1]).
delta([q1],x,[q5, q6, q7]).
delta([q1],y,[q6, q7]).
delta([q1],z,[]).
delta([q5, q6, q7],x,[]).
delta([q5, q6, q7],y,[]).
delta([q5, q6, q7],z,[q1, q2, q3, q4]).
delta([q6, q7],x,[]).
delta([q6, q7],y,[]).
delta([q6, q7],z,[]).
delta([],x,[]).
delta([],y,[]).
delta([],z,[]).
delta([q1, q2, q3, q4],x,[q5, q6, q7]).
delta([q1, q2, q3, q4],y,[q6, q7]).
delta([q1, q2, q3, q4],z,[]).
final_state([q5, q6, q7]).
final_state([q6, q7]).
[~/public_html/4340/f04][1:46pm] mv out.dat m3.pl
[~/public_html/4340/f04][1:46pm] pl
Welcome to SWI-Prolog (Version 3.2.9)
Copyright (c) 1993-1999 University of Amsterdam.  All rights reserved.

For help, use ?- help(Topic). or ?- apropos(Word).

?- ['min.pl'].
min.pl compiled, 0.01 sec, 8,628 bytes.

Yes
?- ['m3.pl'].
m3.pl compiled, 0.00 sec, 2,120 bytes.

Yes
?- minimize.
start_state([[q1, q2, q3, q4], [q1]]).
delta([[q6, q7]],x,[[]]).
delta([[q6, q7]],y,[[]]).
delta([[q6, q7]],z,[[]]).
delta([[q5, q6, q7]],x,[[]]).
delta([[q5, q6, q7]],y,[[]]).
delta([[q5, q6, q7]],z,[[q1, q2, q3, q4], [q1]]).
delta([[q1, q2, q3, q4], [q1]],x,[[q5, q6, q7]]).
delta([[q1, q2, q3, q4], [q1]],y,[[q6, q7]]).
delta([[q1, q2, q3, q4], [q1]],z,[[]]).
delta([[]],x,[[]]).
delta([[]],y,[[]]).
delta([[]],z,[[]]).
final_state([[q6, q7]]).
final_state([[q5, q6, q7]]).

Yes
?- halt.
[~/public_html/4340/f04][1:46pm]