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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Minimization of Finite Automata

  • K. R. Chowdhary

摘要

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.