Abstract: A DFA states minimized algorithm which is suitable for computer implementation and based on states transition matrix is brought forward. In process of finding equivalent states, by writing the state into the state judge list when scanning the states transition matrix, this algorithm can minimize DFA states by scanning the state transition matrix once and using similar storage space to traditional algorithm. By contrast with traditional algorithm, the new algorithm has better time complexity and the same space complexity.

Key words: Deterministic Finite Automata（DFA）, states minimization, states transition matrix

摘要： 提出了一种基于状态转换矩阵的适合计算机实现的DFA状态最小化算法，在计算等价状态过程中，通过记录扫描过程中发现的具有相同输入字符和相同转换状态的状态判定链表，算法可以用一遍扫描和与传统算法相近的存储空间实现DFA状态的最小化。与传统的DFA状态最小化算法相比，该算法具有较好的时间复杂度和相同的空间复杂度。

关键词: 确定有穷自动机（DFA）, 状态最小化, 状态转换矩阵