COMPARATIVE ANALYSIS OF DETERMINISTIC FINITE AUTOMATA MINIMIZATION ALGORITHMS WITH RESPECT TO IMPLEMENTATION EFFICIENCY
Abstract
The problem of minimizing deterministic finite automata, which belongs to the fundamental problems of automata theory and formal languages, is investigated. The practical importance of the minimization problem is associated with syntactic analysis, digital circuit optimization, compiler design, and the construction of search and lexical analyzers. Particular attention is paid to the comparison of the efficiency of implementations of the most common automata minimization algorithms, namely the table-filling method, Hopcroft’s algorithm, and Brzozowski’s algorithm. An experimental study is carried out on several types of deterministic automata, including random automata, lexical automata, automata with high transition density, and automata with a large number of redundant states. For each algorithm, execution time and memory consumption are determined depending on the number of states, the alphabet size, and the nature of transitions between states. Based on the experimental results, it is demonstrated that Hopcroft’s algorithm exhibits the best or near-best performance in most of the considered cases and is characterized by high stability and good scalability as the size of automata increases. The analysis of Brzozowski’s algorithm reveals significant variability in its efficiency, as well as its advantages for automata with a large number of states, alongside a substantial degradation in performance for automata with dense transitions. It is experimentally established that the table-filling method demonstrates the worst scalability and is therefore mainly suitable for automata of small size. The obtained results are consistent with theoretical complexity estimates of the considered algorithms and can be used to justify the selection of a minimization method for deterministic finite automata in practical applications
References
2. Morazán M. T. Programming based formal languages and automata theory: Design, implement, validate, and prove. Springer, 2024. 420 р.
3. Aho A. V., Sethi R., Ullman J. D. Compilers: Principles, techniques, and tools. 2nd ed. Addison-Wesley, 2006. 1024 р.
4. Pin J. É. (Ed.) Handbook of automata theory. European Mathematical Society Publishing House, 2021. 600 р.
5. Hopcroft J. E., Motwani R., Ullman J. D. Introduction to automata theory, languages, and computation. 3rd ed. Pearson Education, 2007. 521 р.
6. Almeida M., Moreira N., Reis R. On the performance of automata minimization algorithms. In Proceedings of the 4th Conference on Computation in Europe: Logic and Theory of Algorithms, 2007. P. 3–14.
7. Hopcroft J. E. An n log n algorithm for minimizing states in a finite automaton. In Theory of machines and computations, 1971. P. 189–196. Elsevier.
8. Martens J. J. M., Wijs A. J. An evaluation of massively parallel algorithms for DFA minimization. Electronic Proceedings in Theoretical Computer Science, 409, 2024. P. 138–153.
9. Heemstra J., Martens J. J. M., Wijs A. J. Evaluating massively parallel algorithms for DFA minimisation, equivalence checking and inclusion checking. arXiv, 2025. URL: https://arxiv.org/pdf/2508.20735 (дата звернення: 14.02.2026).
10. Daci A., Lomont C. DFA minimization: Double reversal versus split minimization algorithms. Theoretical Computer Science, 583, 2015. P. 78–85. https://doi.org/10.1016/j.tcs.2015.04.002
11. Slavici V., Kunkle D., Cooperman G., Linton S. Finding the minimal DFA of very large finite state automata with an application to token passing networks. arXiv, 2011. URL: https://arxiv.org/pdf/1103.5736 (дата звернення: 16.02.2026)
This work is licensed under a Creative Commons Attribution 4.0 International License.
ISSN 
