Two FSM's are said to be *equivalent* if they accept exactly the
same set of strings. Given any nondeterministc FSM, it is always
possible to find an equivalent one that has *no* epsilon
transitions. In fact, given a machine as defined and represented
above, we can easily define such an equivalent epsilon-free machine.
So given a machine named *mach* and defined in m/4, mis/2 and
mfs/2, we will define the transitions, initial state and final state
for its epsilon-free version named *efree(mach)* as follows:

% epsilon-free machines % first define emoves as any sequence of epsilon transitions emoves(_,State,State). emoves(Mach,State0,State) :- emoves(Mach,State0,State1), m(Mach,State1,'',State). % define the transition relation of the efree machine m(efree(Mach),State,Symbol,TargState) :- emoves(Mach,State,State1), m(Mach,State1,Symbol,State2), Symbol \== '', emoves(Mach,State2,TargState). % define the initial and final states of the efree machine mis(efree(Mach),IS) :- mis(Mach,IS). mfs(efree(Mach),FS) :- mfs(Mach,FS1),emoves(Mach,FS,FS1). mfs(efree(Mach),FS) :- mfs(Mach,FS1),emoves(Mach,FS1,FS).

The predicate `emoves/3`

defines for any machine the set of pairs
of states such that the machine can move from the first state to the
second state without consuming any symbols in the input string. Then
with this definition, the rule defining transitions says that an
epsilon-free machine can move from State to TargState on Symbol if it
can move from State to State1 using only epsilon moves, can move from
State1 to State2 on seeing Symbol (which is *not* epsilon) and can
make epsilon moves from State2 to TargState.

The initial state of the epsilon-free machine is exactly the initial state of the original machine. The final state of the epsilon-free machine is any state from which you can get to a final state of the original machine using only epsilon transitions, or any state you can get to from a final state using only epsilon transitions.

For example:

warren% xsb XSB Version 1.6.0 (96/6/15) [sequential, single word, optimal mode] | ?- [automata]. [automata loaded] yes | ?- m(efree(m0s1s2s),So,Sym,Ta),writeln(m(efree(m0s1s2s),So,Sym,Ta)),fail. m(efree(m0s1s2s),q0,0,q0) m(efree(m0s1s2s),q0,0,q1) m(efree(m0s1s2s),q0,0,q2) m(efree(m0s1s2s),q1,1,q1) m(efree(m0s1s2s),q1,1,q2) m(efree(m0s1s2s),q2,2,q2) m(efree(m0s1s2s),q0,1,q2) m(efree(m0s1s2s),q0,1,q1) m(efree(m0s1s2s),q1,2,q2) m(efree(m0s1s2s),q0,2,q2) no | ?- mis(efree(m0s1s2s),IS),writeln(mis(efree(m0s1s2s),IS)),fail. mis(efree(m0s1s2s),q0) no | ?- mfs(efree(m0s1s2s),FS),writeln(mfs(efree(m0s1s2s),FS)),fail. mfs(efree(m0s1s2s),q2) mfs(efree(m0s1s2s),q0) mfs(efree(m0s1s2s),q1) no | ?-

The diagram for `efree(m0s1s2s)`

is shown in Figure
5.2.