Minimization of Finite Automata
摘要
Minimization of a finite automaton, i.e., reducing its total number of states is important—an automata with fever states is more efficient, it requires less memory and less time in recognition of input strings. The basic approach used is often to eliminate states that cannot be reached from start state and to merge the states whose behavior is indistinguishable with each other. The chapter presents approach of NFA homomorphism to merge the indistinguishable states, followed with solved examples and discusses the limitations of this approach. Number of theorems and lemmas have been presented that act as ground work for minimization of finite automata, followed with the famous Myhill–Nerode theorem and its applications. A formalism is presented based on distinguishability, followed with number of worked out exercises and list of other exercises for practice.