一种新的DFA状态最小化算法

计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (1): 47-48.

一种新的DFA状态最小化算法

范书义，孟晨，王成

军械工程学院导弹工程系，石家庄 050003

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2012-01-01 发布日期:2012-01-01

New minimized algorithm of DFA states

FAN Shuyi, MENG Chen, WANG Cheng

Department of Missile Engineering, Ordnance Engineering College, Shijiazhuang 050003, China

Received:1900-01-01 Revised:1900-01-01 Online:2012-01-01 Published:2012-01-01

摘要/Abstract

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

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

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状态最小化算法[J]. 计算机工程与应用, 2012, 48(1): 47-48.

FAN Shuyi, MENG Chen, WANG Cheng. New minimized algorithm of DFA states[J]. Computer Engineering and Applications, 2012, 48(1): 47-48.