免费文档

NFA→FA→GFA自动机转换算法

第34卷 第3期 电 子 科 技 大 学 学 报 Vol.34 No.3 2005年6月 Journal of UEST of China Jun. 2005

NFA→FA→GFA自动机转换算法

周启海

(西南财经大学经济信息工程学院 成都 610074)

【摘要】研究了不确定有穷自动机NFA、确定有穷自动机FA、规范有穷自动机GFA的基本关系与等价转换;给出了“NFA→FA”等价转换算法与“FA→GFA”等价转换算法,构造性证明了从FA到GFA的存在性,提供了自动机极小化算法的研究基础。

关 键 词 不确定自动机; 确定自动机; 规范自动机; 等价转换算法; 极小化 中图分类号 TP301.1 文献标识码 A

Automata Transform Algorithm for“NFA→FA→GFA”

ZHOU Qi-hai

(School of Economic Information Engineering, Southwestern University of Finance and Economics Chengdu 610074)

Abstract The essential relationship and equal value transformation of Non-Finite Automat, Finite Automat and Gauge Finite Automat (abbreviated as NFA, FA & GFA) is studied. An equal value transforming algorithms of "NFA→FA” and "FA→GFA” are given, the existing nature from FA To GFA is proved by construction, with which the basis of an algorithm research on the minimum of an Automat is provided.

Key words non-finite automat; finite automat; gage automat; equal value transforming algorithm; minimum

文献[1~7]论及不确定有穷自动机“NFA(Non-Finite Automat)确定有穷自动机→FA(Finite Automat)规范有穷自动机→GFA(Gage Finite Automat)”等价转换,但存在不足:仅有公理化结论,而未见构造性算法,且在“FA→GFA”等价转换理论证明中存在不严谨之处[1]。为此,本文给出“NFA→FA→GFA”自动机自动转换算法的构造、证明与改进。

1 NFA转化为等价的FA

定义 1 不确定有穷自动机NFA,是定义在字母表∑上的数学系统(K,∑,δ,Q0,F);确定有穷自动机FA,是定义在字母表∑上的数学系统(K,∑,δ,q0,F);其中,K是非空有穷状态集,∑是非空有穷输入字母表,δ是K×∑到K的映射,开始状态集Q0∈2K,开始状态q0∈K,终止状态集F K。若有穷自动机M1、M2所能接受的语言分别为T(M1)、T(M2)满足T(M1)=T(M2),则称M1与M2等价。

定理 1 任给NFA,必存在等价于它的FA。

文献[1]证明了定理1。构造了如图1所示的“NFA→FA”算法1;图中:[Q]、[Qi]为工作栈B、D中元素,W为陷阱状态集。

基于定理1和算法1:不失一般性,可将NFA极小化问题归结为FA极小化问题。 收稿日期:2004 03 01

作者简介:周启海(1947 ),男,教授,主要从事软件设计方法学等方面的研究.

相关文档
热门文档
你可能喜欢
  • 马丁格文犯罪者动机
  • ugly betty剧本
  • c算法
  • fp+tree算法优缺点
  • 哈希算法new
  • pi算法
评论