Analysis of blow-up situation in finite automata
Annotatsiya
The blow-up phenomenon in finite automata is one of the most far reaching and significant problems in formal language theory and system design based on automata. Discovering a nondeterministic finite automaton (NFA) transformed into an equivalent deterministic finite automaton (DFA) with the famous powerset construction can lead to an exponentially larger number of states and this phenomenon is known as the state explosion, which makes solving even moderately sized input automata computationally infeasible. This issue is also known as the blow-up problem and has far reaching consequences on the compilation design, pattern matching engines, model checking systems, natural language processing pipelines, and network intrusion detection systems. The interaction between descriptional complexity and operational complexity with mitigating strategies despite decades of theoretical exploration has not been fully synthesized in the light of an emerging computational requirement. The review is a systematic literature review of articles published as early as 2019 and 2025 to identify the contemporary picture of the analysis of blow-ups in finite automata. The paper also determines the mathematical properties of exponential blowup; it discusses the effectiveness of modern heuristic and algebraic mitigation strategies. It has been shown in the analysis that the worst-case exponential lower bounds are tight in proving that classical NFA to DFA conversion is impossible, although in practice the improvements of up to 40-60% are possible by using state-aware lazy determinization and simulation-based reduction.