CSc 8710
Fall 2003
HW 3 (Due: Tuesday, 30 September)
----------------------------------

Remove Empty Transitions in an NFA
NFA (with-e) to NFA (without-e) CONVERSION
-------------------------------------------

Script started on Mon Jan 20 13:20:17 199
> more m1.pl
start_state(q0).
final_state(q2).
delta(q0,nil,q1).
delta(q0,a,q3).
delta(q1,a,q4).
delta(q1,b,q2).
delta(q3,nil,q1).
delta(q3,b,q4).
delta(q4,nil,q5).
> pl
| ?- ['rmet.pl'].
rmet.pl consulted 344 bytes 0.0333333 sec.

yes
| ?- ['m1.pl'].
m1.pl consulted 344 bytes 0.0333333 sec.

yes
| ?- rm_etrans.

yes
| ?- halt.

[ Prolog execution halted ]
> more out.dat
start_state(q0).
delta(q0,a,q1).
delta(q0,a,q3).
delta(q0,a,q4).
delta(q0,a,q5).
delta(q0,b,q2).
delta(q1,a,q4).
delta(q1,a,q5).
delta(q1,b,q2).
delta(q3,a,q4).
delta(q3,a,q5).
delta(q3,b,q2).
delta(q3,b,q4).
delta(q3,b,q5).
final_state(q2).
>

NFA to DFA Conversion
NFA (without-e) to DFA CONVERSION
----------------------------------

>more nfa1.pl
start_state(q0).
final_state(q1).
delta(q0,a,q0).
delta(q0,a,q1).
delta(q0,b,q0).
>pl
| ?- ['ntd.pl'].
ntd.pl consulted 184 bytes 0.0166667 sec.

yes
| ?- ['nfa1.pl'].
nfa1.pl consulted 184 bytes 0.0166667 sec.

yes
| ?- convert.

yes
| ?- halt.

[ Prolog execution halted ]
>more out.dat
start_state([q0]).
delta([q0],a,[q0,q1]).
delta([q0],b,[q0]).
delta([q0,q1],a,[q0,q1]).
delta([q0,q1],b,[q0]).
final_state([q0,q1]).