Minimization of Nondeterministic Finite Automata Using Graph Based Optimization Techniques

Abstract

Nondeterministic finite automata (NFAs) are commonly used to model regular languages in text
processing, compiler construction, model checking and pattern matching. Unlike the deterministic
finite automata, an NFA may contain multiple transitions on the same input symbol, and can have
more than one state active during the execution. This nondeterminism can be useful to represent
things succinctly, but is also hard to do exactly in the computer. In this paper, graph-based
optimization methods for NFAs to reduce the size without compromising the accepted language
are explored. The paper covers equivalence based reduction, simulation and preorder relations,
bisimulation, graph decomposition and heuristic state merging. It highlights the principal
difficulties in exact minimization, such as high computational costs, maintaining language
equivalence, scalability at large automata and processing time reduction and quality balance. A
methodology to evaluate graph-based NFA reduction techniques is suggested, which is
reproducible and considers state reduction, transition reduction, equivalence verification, memory
usage and runtime. The paper is concluded that graph based techniques are best used as
reasonable approximation and pre-processing methods, where formal guarantees are needed
exact verification is applied.