Next: Per subset and per Up: Variants for -Moves Previous: Variants for -Moves

## Per graph

In the per graph variant two steps can be identified. In the first step, efree, an equivalent -free automaton is constructed. In the second step this -free automaton is determinised using the subset construction algorithm. The advantage of this approach is that the subset construction algorithm can remain simple because the input automaton is -free.

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:

• efreet: , where , and .
• efrees: , where , and .

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.

Next: Per subset and per Up: Variants for -Moves Previous: Variants for -Moves

2000-07-10