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, efree^{t} might introduce states which are not co-accessible: states from which no path exists to a final state; in contrast, efree^{s} 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 efree^{t,c} ensures that all states in the resulting automaton are co-accessible; efree^{s,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 efree^{t,c} is employed, because states which were not co-accessible (in the input) are removed (this is therefore an additional benefit of efree^{t,c}; the fact that efree^{s,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 efree^{t} in combination with the subset-construction algorithm generally produces smaller automata than efree^{s} (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 graph^{X} to indicate the non-integrated algorithm based on efree^{X}.