ПОРІВНЯЛЬНИЙ АНАЛІЗ АЛГОРИТМІВ МІНІМІЗАЦІЇ ДЕТЕРМІНОВАНИХ СКІНЧЕННИХ АВТОМАТІВ ЗА ОЦІНКОЮ ЕФЕКТИВНОСТІ РЕАЛІЗАЦІЇ

Є. В. Тиш

doi:10.32782/2521-6643-2026-2-72.24

Є. В. Тиш Тернопільський національний технічний університет імені Івана Пулюя https://orcid.org/0000-0001-6420-7623

DOI: https://doi.org/10.32782/2521-6643-2026-2-72.24

Ключові слова: детерміновані скінченні автомати, мінімізація, еквівалентні стани, метод розмітки таблиці, алгоритм Хопкрофта, алгоритм Бржозовського, час виконання алгоритму, обчислювальна складність

Анотація

В статті досліджено задачу мінімізації детермінованих скінченних автоматів, яка відноситься до основних проблем теорії автоматів та формальних мов. Практична важливість задачі мінімізації має значення для синтаксичного аналізу, оптимізації цифрових схем, проєктування компіляторів та побудови пошукових, а також лексичних аналізаторів. Основну увагу статті приділено порівнянню ефективності реалізації найпоширеніших алгоритмів мінімізації автоматів: методу розмітки таблиці, алгоритму Хопкрофта та алгоритму Бржозовського. Експериментальне дослідження виконано на кількох типах детермінованих автоматах, зокрема, випадкових автоматах, лексичних автоматах, автоматах із високою щільністю переходів, а також автоматах з великою надмірністю станів. Для кожного алгоритму визначено час виконання та обсяг використаної оперативної пам’яті залежно від кількості станів, розміру алфавіту та характеру переходів між станами. На основі експериментальних результатів доведено, що алгоритм Хопкрофта володіє найкращою або близькою до найкращої продуктивністю у більшості досліджених випадків та характеризується високою стабільністю й хорошою масштабованістю при зростанні розміру автоматів. Показано значну варіативність ефективності алгоритму Бржозовського, його переваги для автоматів з великою кількістю станів, однак суттєве погіршення показників для автоматів із щільними переходами. Експериментально встановлено, що метод розмітки таблиці характеризується найгіршими показниками масштабування, тому він є доцільним переважно для автоматів невеликого розміру. Отримані результати узгоджуються з теоретичними оцінками складності розглянутих алгоритмів та можуть бути використані для обґрунтованого вибору методу мінімізації детермінованих скінченних автоматів у практичних застосуваннях

Посилання

1. Kumar S., Kumar J., Dubey S. S., Pathak V. N. Theory of automata and its applications in science and engineering. Deep Science Publishing, 2025. 350 р. URL: https://doi.org/10.70593/978-93-49910-92-8 (дата звернення: 14.02.2026)
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)