关键词: 确定型有穷自动机, 非确定型有穷自动机, 等价关系, 状态极小化

Abstract: The automaton state set can be minimized based on the equivalence relation, so that a minimized automaton can be obtained. The link operation is that the execution will shift to the second automaton unconditionally as soon as the first DFA has finished its execution. A nondeterministic finite automaton (NFA) can be constructed by linking two deterministic finite automata (DFAs). At the same time, the NFA’s equivalence relation can be constructed based on the two DFAs’ equivalence relation, so that we can minimize this NFA. Moreover, several conclusions have been obtained in this paper. The first one is that the number of states of the minimal automaton of the NFA is not more than the counterpart of the NFA which is constructed by linking the two minimal automata of the two DFAs. The second one is that the language which is identified by automaton is unchangeable in the course of minimizing.

Key words: deterministic finite automaton, nondeterministic finite automaton, equivalent relation, minimal state