基于前序关系的非确定型有穷自动机极小化算法

J4 ›› 2010, Vol. 45 ›› Issue (7): 34-38.

基于前序关系的非确定型有穷自动机极小化算法

张明明,秦永彬

贵州大学计算机科学与信息学院, 贵州贵阳 550025

收稿日期:2010-04-02 出版日期:2010-07-16 发布日期:2010-09-06
作者简介:张明明(1979-),男,硕士研究生,研究方向为可计算性与计算复杂性.Email:fysfzmm@163.com
基金资助:
贵州省自然科学基金资助项目(黔科合J字［2007］2203号);贵州省省长基金资助项目(黔科教办［2004］04号);贵州大学自然科学青年基金资助项目(贵大自青基合字［2009］021号);贵州大学研究生创新基金资助项目(校研理工［2010］035号)

A non-deterministic finite automata minimization method based on preorder relation

ZHANG Ming-ming, QIN Yong-bin

College of Computer Science and Information, Guizhou University, Guiyang 550025, Guizhou, China

Received:2010-04-02 Online:2010-07-16 Published:2010-09-06

摘要/Abstract

摘要：

为了减少非确定型有穷自动机(non-deterministic finite automata,NFA)的状态数,引入前序关系,并以图论为工具,将NFA的转移图看作一个带有标记的有向图,给出了NFA极小化的一个新方法。与现行的利用归并等价状态来极小化NFA的算法相比,该方法可以使得NFA在接受语言的能力等价的前提下,状态数得到进一步的减少。

关键词: 非确定型有穷自动机;前序关系;状态合并;极小化

Abstract:

In order to reduce the number of non-deterministic finite automata (NFA) states, the preorder relation was introduced. The transition diagram for the NFA was regarded as a directed graph with signs based on graph theory,and then a new method of NFA minimization was proposed. Compared with the current NFA minimization algorithm based on merging the equivalent states, this method could further reduced the number of NFA states while accepting the same languages.

Key words: non-deterministic finite automata; preorder relation; state merging; minimization

张明明,秦永彬. 基于前序关系的非确定型有穷自动机极小化算法[J]. J4, 2010, 45(7): 34-38.

ZHANG Ming-ming, QIN Yong-bin. A non-deterministic finite automata minimization method based on preorder relation[J]. J4, 2010, 45(7): 34-38.

参考文献

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed