一种非确定型有穷自动机的极小化方法  

A Minimization Method of Non-deterministic Finite Automata

作　　者：张丽[1] 

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

出　　处：《宁夏大学学报（自然科学版）》2012年第2期148-151,共4页Journal of Ningxia University(Natural Science Edition)

基　　金：国家自然科学基金资助项目(60863005;61011130038);贵州省自然科学基金(黔科合J字[2007]2203号)

摘　　要：自动机状态极小化是寻求状态数较少的自动机,使其与原自动机接受相同的语言.确定型有穷状态自动机(DFA)极小化问题在平方时间内可解,通过状态集上引入等价关系导出的商自动机即为接受相同正则语言的极小化自动机.而非确定型有穷状态自动机(NFA)极小化问题尚未找到有效算法.尽管NFA可以转化为DFA且接受的语言不变,但可能会出现状态数指数级增加.从语言B可以构造一个接受自己的子语言自动机,同态压缩映射子语言自动机为最终系统,从而为接受语言B的极小化自动机.Automata state minimization is to find an automata which have the less number of states, and accepted the same language with the original automata. The minimization problem of deterministic finite automata（DFA） can be solved in time square. Quotient automata is derived by introducing the equivalence relation in state set, which is a minimized automata accepted the same regular language. However the minimization problem of non-deterministic finite automata（NFA） has not yet found an effective method. Although a NFA can turn to a DFA and accept the same language, the number of states appears to increase exponentially. Language B can construct a sub-language automata to accept the same language, and get homomorphic contracting mapping sub-language automata as the final system. Then the minimized automata can accept B.

关 键 词：自动机 非确定型自动机 子语言自动机 同态 极小化 

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