An algorithm for efree is described for
instance in [8][page 26-27]. The main
ingredient of efree is the construction of the function
-CLOSURE, which can be computed by using a standard transitive
closure algorithm for directed graphs: this algorithm is applied to
the directed graph consisting of all
-moves of M. Such an
algorithm can be found in several textbooks (see, for instance,
[5]).
For a given finite-state automaton
efree
computes
, where
,
, and
.
Instead of using
-CLOSURE on both the source and target side
of a transition, efree can be optimised in two different ways by
using
-CLOSURE only on one side:
Although both variants appear very similar, there are some differences. Firstly, efreet might introduce states which are not co-accessible: states from which no path exists to a final state; in contrast, efrees might introduce states which are not accessible: states from which no path exists from the start state. A straightforward modification of both algorithms is possible to ensure that these states are not present in the output. Thus efreet,c ensures that all states in the resulting automaton are co-accessible; efrees,a ensures that all states in the resulting automaton are accessible. As a consequence, the size of the determinised machine is in general smaller if efreet,c is employed, because states which were not co-accessible (in the input) are removed (this is therefore an additional benefit of efreet,c; the fact that efrees,a removes accessible states has no effect on the size of the determinised machine because the subset construction algorithm already ensures accessibility anyway).
Secondly, it turns out that applying efreet in combination with the subset-construction algorithm generally produces smaller automata than efrees (even if we ignore the benefit of ensuring co-accessibility). An example is presented in figure 2. The differences can be quite significant. This is illustrated in figure 3.
Below we will write per graphX to indicate the non-integrated algorithm based on efreeX.
![]() |
![]() |