基于等价关系的有穷自动机最小化方法

基于等价关系的有穷自动机最小化方法
作者：马子睿
来源：《电脑知识与技术》2009年第25期
摘要:主要介绍了有穷自动机的基础知识,研究了有穷自动机的等价性,并在确定型有穷自动机的状态集上引入等价关系,给出了自动机的最小化过程。

利用等价归并算法,可以将某一给定的确定型有穷自动机状态集上的等价状态归并掉,生成与其等价的最小化的确定型有穷自动机。

关键词:有穷自动机;状态转换图;等价关系;确定型有穷自动机;最小化
中图分类号:TP312文献标识码:A文章编号:1009-3044(2009)25-7273-01
Finite Automata Minimization Based on Equivalence Relation
MA Zi-rui
(School of Mathematics and Computer Science, Ningxia University, Yinchuan 750021, China)
Abstract: The paper introduce the foundation knowledge of finite automata and research the equivalence of finite automata. We import equivalence relation in the set of state of DFA and give the procedure of minimum automata. Using the equivalence merger algorithm, we can merge the equivalent state s in the set of the automaton’s states and then get the minimized automaton which is equivalent to the original automaton.
Key words: finite automata; state transform figure; equivalence relation; DFA; minimization
有穷自动机是计算机软、硬件研究的重要基础理论,它在软件设计中的应用,为设计者提供了一种新的解决问题的思想和方法[1]。

它具有任意有限数量的内部格局或状态,用此来记忆过去输入的有关信息,根据当前的输入可确定下一步的状态和行为。

一个有穷自动机等价于一个状态转换图。

这样得到的状态转换图可以应用有穷自动机的有关定理和算法进行等价变换、约简,然后用程序实现。

由于状态转换图与程序有一定的对应关系,所以使得程序设计比较规范化,从而高效的完成了软件设计工作。

1 有穷自动机
给定有限集Σ是一个字母表,Σ*是字母表Σ上有穷符号串构成的集合,ε表示空串,串w的长度表示成|w|。

Σ上的语言是Σ*的子集,Σ上的正则表达式可以是Φ,ε或a∈Σ或使用以下规则的有限次的组合:给两个正则表达式α与β,并α+β,差α-β,星运算α*也是正则表达式。

正则表达式用α或R表示L(α)表示定义在正则表达式α上的语言[2-3]。

定义1一个有穷自动机M是一个五元组M=(Q,Σ,δ,q0,F),其中:
l) Q是一个有穷的状态集合;
2) Σ是一个有穷的输入符号集合;
3) δ?哿Q×(Σ∪{ε})×Q是转移函数,以一个状态和一个输入符号作为变量,返回状态;
4) q0∈Q是一个初始状态;
5) F?哿Q是一个终结状态集;
定义2如果δ:Q×Σ→Q,称自动机M是确定型有穷自动机(DFA)。

如果δ:Q×Σ×Q,称自动机M是非确定型有穷自动机(NFA)。

如果在δ上没有限制,称自动机M是带ε转移的非确定型有穷自动机(ε-NFA)。

2 等价性
在研究有穷自动机与正则表达式的关系时,一般引入状态转换图概念,并扩充这一概念,使图中每条边标记为字母表Σ上的字符串或空字ε,称扩展的转换图,任一扩展的转换图都可转换成等价的ε-自动机,ε-自动机是一种包含空字ε的特殊的自动机。

任意一个自动机都可转换为等价的确定有穷自动机DFA,而确定有穷自动机DFA与正则集之间存在等价关系,即:假定V=L(R),R 是正则集V相对应的正则表达式。

Σ上的一个字集V?奂Σ*是正则的充分必要条件,是存在Σ上的确定有限自动机DFA M使得:V=L(M)。

对于任一给定的确定有穷自动机DFA M,存在一个正则表达式R,使得L(M)=L(R),反之亦然[2-4]。

3 确定型有穷自动机的最小化
有穷自动机的最小化是一个十分重要的问题。

这里所说的最小化是指在等价的前提下,对有穷自动机进行转换,使得经转换所得到的有穷自动机状态结点最少,但它仍然与原来有穷自动机等价。

3.1 最小化过程
M=(Q,Σ,δ,q0,F)是一个有穷自动机。

M的状态转移图如图1所示。

为了最小化M,考虑状态A与G,从图1上可以看
到:δ*(A,0)={B},δ*(G,0)={G},δ*(A,01)={C}∈F,δ* (G,01)=E?埸F,证明A与G可区分的,即A与G不是等价的。

相反,考虑状态A与E,从图1上可以看
到:δ*(A,00)={G},δ*(E,00)={G},δ*(A,01)={C},δ* (E,01)={C},以0开头的串都能将A,E带到同一状态,且δ*(A,10)={C},δ* (E,10)={C},δ*(A,11)={G},δ* (E,11)={G},以1开头的串都能将A,E带到同一状态,足以证明A与E是不可区分的,即A与E是等价的[5-6]。

这样,据同样的算法来求出可区分状态对。

最后,可知(A,E)(H,B)(F,D)具有等价关系。

于是形成一个等价类划分
[A,E][H,B][F,D][C][G]。

从而得到图1经过最小化的自动机M’如图2所示。

3.2 最小化算法
归并等价状态的DFA最小化算法描述如下:
1) 通过等价关系≈r,找出所有等价状态对;
2) 通过1)把状态集Q划分成互相等价的状态的块。

此时,块中所含的状态是互相等价的,不同块中的状态是可互相区别的[7-8];
3) 用块作为状态来构造最小化自动机。

4 结束语
有穷自动理论给出了一类计算模型,这种模型在计算机科学的若干应用领域都有着重要的作用。

确定型有穷自动机最小化的关键是在其状态集上引入等价关系,利用等价性,右同余求出状态集中所有的等价类来实现自动机的最小化。

一般来说,自动机的状态结点越少,意味着越节省软件和硬件资源,实现它的程序也越简练。

参考文献:
[1] 严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社,1997.
[2] 吕映芝,张素琴.编译原理[M].北京:清华大学出版社,2003.
[3] Aho A V,Sethi R,Ullman J D.编译原理[M].李建中,姜守旭,译.北京:机械工业出版社,2004.
[4] 耿素云.集合论与图论[M].北京:北京大学出版社,2000.
[5] 丁春欣.有限自动机的最小化[J],高等理科学刊,2000,20(3):8-10.
[6] 徐江.对确定有限自动机最小化算法的改进[J].桂林航天工业高等专科学校学
报,2005(4):14-16.
[7] 宿云.确定型有穷自动机最小化算法的三点说明[J].信息技术,2005,34(6):41-52.
[8] 戚国正,杨崇耀.关于概率自动机的等价性与极小化问题[J].贵州科学,1994,12(1):8-11.。