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

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