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

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

作　　者：张明明[1] 秦永彬[1] 

机构地区：[1]贵州大学计算机科学与信息学院,贵州贵阳550025

出　　处：《山东大学学报（理学版）》2010年第7期34-38,共5页Journal of Shandong University(Natural Science)

基　　金：贵州省自然科学基金资助项目(黔科合J字[2007]2203号);贵州大学自然科学青年基金资助项目(贵大自青基合字[2009]021号);贵州省省长基金资助项目(黔科教办[2004]04号);贵州大学研究生创新基金资助项目(校研理工[2010]035号)

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

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]