A deterministic FSM is a machine such that for every state for any symbol there is at most one transition from that state labeled with that symbol (and there are no epsilon transitions.) This means that there is never a choice in how the machine is to proceed when it sees a symbol: there will be at most one state to move to given that symbol. The question arises as to whether given an arbitrary FSM there is always an equivalent deterministic FSM, i.e., a deterministic FSM that accepts the same language, i.e., exactly the same set of strings.

The answer turns out to be ``yes'', and it is not difficult to see
why. Given a nondeterministic (ND) machine, we can construct a
deterministic machine each of whose states corresponds to a set of
states in the nondeterministic machine. The idea is that, after
seeing a string, the deterministic machine will be in a state
corresponding to a set of ND states just in case the ND FSM could be
in any one of the ND states after seeing the same string. As a very
trivial example, say we had a ND machine with three states: *q*1,
*q*2, *q*3, with *q*1 the initial state and transitions from *q*1 to
*q*2 on symbol *a* and from *q*1 to *q*3 also on *a*. Then the
deterministic machine would have two states,
and
(each being a set of the original machine's states), and a transition
from the first to the second on symbol *a*.

The following specification describes this construction. Rather than
constucting *all* the states (which would necessarily be
exponential in the number of states in the nondeterministic machine),
we will only construct those that are reachable from the initial
state. This may be a much smaller number. Also, for this particular
specification to be constructive, we need to constrain the set of
possible deterministic states in some way, and this seems a good way.

We will assume that the machine is an epsilon-free machine. If
`efreemach`

is the name of an epsilon-free machine then
`det(efreemach)`

is the name of an equivalent deterministic
machine.

:- import member/2 from basics. :- import tsetof/3 from setof. % Assume Mach is an epsilon-free machine. % A state is reachable if it is the initial state or if it can be % reached by one step from a reachable state. reachable(Mach,S) :- mis(Mach,S). reachable(Mach,S) :- reachable(Mach,S1),m(Mach,S1,_,S). % The next state of the deterministic machine given a state and symbol % is the set of states of the nondeterministic machine which are a % next state starting from some element of the current state of the % deterministic machine. (Mach is assumed to be epsilon-free.) m(det(Mach),State0,Sym,State) :- reachable(det(Mach),State0), tsetof(NDS, a_next(Mach,State0,Sym,NDS), State). % A state is a next state if it is a next state reachable in one step % from some member of the current state of the deterministic machine. a_next(Mach,DState,Sym,NDState) :- member(S1,DState), m(Mach,S1,Sym,NDState). % The initial state is the singleton set consisting of the initial % state of the nondeterministic machine. mis(det(Mach),[IS]) :- mis(Mach,IS). % A final state is a reachable deterministic state that contains some % final state.of the nondeterministic machine. mfs(det(Mach),FS) :- mfs(Mach,NFS), reachable(det(Mach),FS),member(NFS,FS).

Now we can use this specification to find a deterministic machine that
is equivalent to the nondeterministic machine *m*0*s*1*s*2*s*:

| ?- m(det(efree(m0s1s2s)),S,Sy,T),writeln(m(det(m0s1s2s),S,Sy,T)),fail. m(det(m0s1s2s),[q0],0,[q0,q1,q2]) m(det(m0s1s2s),[q0],1,[q1,q2]) m(det(m0s1s2s),[q0],2,[q2]) m(det(m0s1s2s),[q0,q1,q2],0,[q0,q1,q2]) m(det(m0s1s2s),[q0,q1,q2],1,[q1,q2]) m(det(m0s1s2s),[q0,q1,q2],2,[q2]) m(det(m0s1s2s),[q1,q2],1,[q1,q2]) m(det(m0s1s2s),[q1,q2],2,[q2]) m(det(m0s1s2s),[q2],2,[q2]) no | ?- mis(det(efree(m0s1s2s)),S),writeln(mis(det(m0s1s2s),S)),fail. mis(det(m0s1s2s),[q0]) no | ?- mfs(det(efree(m0s1s2s)),S),writeln(mfs(det(m0s1s2s),S)),fail. mfs(det(m0s1s2s),[q1,q2]) mfs(det(m0s1s2s),[q0,q1,q2]) mfs(det(m0s1s2s),[q2]) mfs(det(m0s1s2s),[q0]) no | ?-

The diagram for `det(efree(m0s1s2s))`

is shown in Figure
5.3.