Conclusion

We have discussed three variants of the subset-construction algorithm for determinising finite automata. The experiments support the following conclusions:

• the per graph variant works best for automata with a limited number of jumps
• the per subset variant works best for automata with a large number of jumps
• the per state variant almost never outperforms both of the two other variants
• typically, if the deterministic jump density of the input is less than 1, then the per graph variant outperforms the per subset variant. If this value is larger than 1.5, then per subset outperforms per graph.
• the per subset approach is especially useful for automata generated by finite-state approximation techniques, because those techniques often yield automata with very large number of $\epsilon$-moves.