COMPARATIVE ANALYSIS OF DETERMINISTIC FINITE AUTOMATA MINIMIZATION ALGORITHMS WITH RESPECT TO IMPLEMENTATION EFFICIENCY - Tysh , Ie. V. (Systems and Technologies, 2026)
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