1998
年 8月
第24卷 第4期
北 京 航 空 航 天 大 学 学 报
JournalofBeijingUniversityofAeronauticsandAstronautics
August 1998
Vol.24 No.4
收稿日期: 1998-05-11 作者 女 50岁 副教授 100083 北京
构造正则
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
达式的简化DFA算法
檀凤琴
(北京航空航天大学 计算机科学与
工程
路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理
系)
摘 要 介绍了构造等价于给定正则表达式的简化确定有限自动机(DFA)的
算法.方法是首先构造与正则表达式等价的非确定有限自动机(NFA),这里省略了
构造带ε动作的有限自动机的操作,然后用状态树构造与该NFA等价的简化DFA.
这个算法在计算机上已实现,并且对输入的任意正则表达式,都可以输出等价于正
则表达式的简化DFA.该算法可以用于某些离散信息处理系统的
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
与分析.
关键词 有限自动机;状态;状态
函数
excel方差函数excelsd函数已知函数 2 f x m x mx m 2 1 4 2拉格朗日函数pdf函数公式下载
;识别;状态图
分类号 TP301.1
有限自动机(FA)理论对正则语言的研究和
某些算法的分析、设计是必不可少的.其中,由正
则表达式构造FA的算法应用较广泛.算法的思
想是根据正则表达式的递归定义,按照正则表达
式的构成层次进行归纳构造.其核心是2个FA
进行连接、∪(并)和*(闭包)运算.一般方法是:
先构造带ε动作的FA,再构造与其等价的非确定
有限自动机(NFA),最后 再由NFA构造与其等
价的确定有限自动机(DFA)[1].当正则表达式的
构成层次较多时,上述方法就显得很繁琐.如果略
去构造带ε动作的FA的操作,就会大大简化由
正则表达式构造DFA的算法.文献[2]中介绍了
有关算法,但算法有误.本文介绍的算法省略了构
造带ε动作的自动机的操作,同时对所求的DFA
作了简化.
1 有关定义和定理
定义1 非确定有限自动机(NFA)是一个五
元组
A=
其中 Q———状态的非空有限集;Σ———输入字母
表;δ———Q×Σ→ρ(Q),称δ为状态函数,ρ(Q)为
Q的幂集;Q1———始态集合,Q1⊆Q 且Q1≠∅;
F———终态集合,F⊆Q.
若对每个q∈Q 和a∈Σ,δ(q,a)是单元素
集,并且Q1为单元素集,则上述五元组称为确定
有限自动机(DFA),通常记作 M.显然DFA是
NFA的特例.对于DFA,若δ(q,a)={q′},常简
单地说δ(q,a)=q′;若Q1={q1},常将{q1}记为
q1.
一个FA常用状态图表示,其中始态用箭头
标出,终态用双圆圈标出.
定义2 设A=是一 NFA,
对任意输入字符串α∈Σ*,如果δ(Q1,α)∩F≠
∅,则称α可被A 识别.
可以被FAA识别的字符串的全体,称为A
的可识别字符串集,记作T(A).
定理1 对于任意 NFA,都存在一个 DFA
与其等价(识别同一字符串集).
证明 设A=是一个 NFA,
构造DFA M 如下:
M=
其中 Q′=ρ(Q);δ′———Q′×Σ→Q′,δ′({q1,q2,
…,qi},a)=δ({q1,q2,…,qi},a);q′1=Q1;F′=
{P|P⊆Q,且P∩F≠∅}.
由定义2,显然M 和A 等价. 证毕
FA识别的字符串集合称为正则集合,正则
表达式是正则集合的一种表示.
2 算 法
对任何正则表达式R,可以构造出识别它所
代表集合的FA[3],按照正则表达式的构成层次
归纳构造如下:
1)归纳基础 图1a~图1c所示的DFA,显
然分别识别ε,∅和单个字符a所代表的集合.
aR=ε bR=∅
2)归纳 设识别正则表达式R1和R2所代表
cR=a
图1 归纳基础中的DFA
集合的DFA都已经构造出来了,由于状态可以
重新命名,不妨设Q1∩Q2=∅,那么,一定能够
构造出识别R1R2、R*1 、R1∪R2所代表集合的
DFA.方法是先构造它们的NFA,然后再由NFA
构造与其等价的简化DFA.首先介绍由 NFA构
造与其等价的简化DFA的算法.
算法1 由NFA构造与其等价的简化DFA
的算法[4].
1)按下述规则构造给定NFAA的状态树.
(1)把A的始态集作为树根(为了简便,将集
合的括号“{ }”略去,只写状态,以下同).
(2)对每一个没有作为分支结点出现过的叶
结点画出对应于每一个输入字符的分支,每个分
支以输入该字符时所有可能转入的状态构成的集
合作为该分支的叶.
(3)如果已构造出了所有第i层的叶,则按
(2)的方法画出第i+1层的叶,如此做下去,直至
每一叶都作为分支结点出现过为止.
2)将树的每个不同结点各作为一个新的状
态.如果结点中含有A 的终态(在状态树中含有
终态的结点下边划有横线),则以该结点作为所求
DFA的终态.根结点作为DFA的始态.
3)将等价状态合并,合并规则如下:
对任意一对状态qi和qj,如果qi和qj均为终
态或均为非终态,并且对∀a∈Σ,满足下列规则
之一,则将qi和qj合并为一个状态.
(1)δ(qi,a)=δ(qj,a);
(2)δ(qi,a)=qi,δ(qj,a)=qj;
(3)δ(qi,a)=qj,δ(qj,a)=qi.
对于进行状态合并后得到的DFA反复进行
状态合并,直到没有满足合并规则的状态为止.
4)由状态树画出待求DFA的状态图.
算法2 由R1,R2的FAAR1和AR2构造R1
R2的DFA的算法.
1)构造R1R2的NFAA.
(1)分别画出AR1和AR2的状态图.
(2)对AR1的所有终态都添加上与AR2的始
态相同的转移弧.
(3)以AR1的始态作为A 的始态,以AR2的
终态作为A的终态.若AR2的始态兼为AR2的终
态,则AR1的终态也作为A的终态.
2)利用算法1构造与A等价的DFA.
例1 设R1=a*ba*,R2=(ba*ba*)*,试构
造R1R2的FA.
解 (1)画出R1和R2的DFAA1和A2,如图
2实线所示.由A1的终态q2引出与A2始态相同
的转移弧,如图2的虚线所示.图2即为识别R1
R2的NFA,其中q1为始态,q2、q3、q5为终态.
(2)画状态树,如图3a.
(3)合并等价状态.观察图3a,{q2}≡{q5}
(对b符合合并规则(1),对a符合合并规则(2)),
将q2和q5记为p2,见图3b.又有{q1}≡{q4}(对b
图2 例1中的NFA
a图2的状态树
bq2和q5合并后的状态树 cq1和q4合并后的状态树
图3 例1中的状态树
符合规则(1),对a符合规则(2)),将q1和q4记为
p1,见图3c,即得所要求的FA,如图4所示.
算法3 由R 的FA构造R*的DFA的算
法.
1)构造识别R*的NFA.
(1)对R的FAAR的所有终态,均添加与AR
694 北 京 航 空 航 天 大 学 学 报 1998年
图4 例1中的简化DFA
的始态相同的转移弧.
(2)增加状态q0,从q0出发添加与AR的始态
相同的转移弧.
(3)把q0作为AR*的始态兼终态,AR的所有
终态都作为AR*的终态.
2)利用算法1,构造与AR*等价的DFA.
例2 令R=0*10*1*,求识别R*的FA.R
的FAAR如图5中实线所示.
解 构造NFAAR*,如图5中添加虚线后所
示的FA,画出状态树,如图6所示.在图6中,有
{q2}≡ {q1,q2}≡ {q2,q3}
令
p0={q0}
p1={q1}
图5 例2中的NFA
图6 例2中的状态树
p2={q2}={q1,q2}={q2,q3}
即得所要求的DFA,如图7所示.
图7 例2中的简化DFA
算法4 由R1和R2的FA构造R1∪R2的
DFA算法.
1)构造R1∪R2的NFAAR.
(1)AR1和AR2的始态都作为AR的始态.
(2)AR1和AR2的终态都作为AR的终态.
2)利用算法1,构造与AR等价的DFA.
例3 令R1=01*,R2=(01)*,求R=R1∪
R2的FA.
解 识别R1和R2的FAA1和A2(见图8).
把它们看成一个NFA,q1,q3为始态,q2和q3是终
态,就得到了识别R1∪R2的NFAAR.画出AR的
状态树,如图9所示.本例中无等价状态可合并.
令
p1={q1,q3}
p2={q2,q4}
图8 例3中的NFA
图9 例3中的状态树
(q⌀为自锁态,图8中没画出它)
p3={q2,q3}
794第4期 檀凤琴:构造正则表达式的简化DFA算法
p4={q4}
p5={q2}
p6={q3}
即得所要求的DFA(见图10).
图10 例3中的简化DFA
3 结 束 语
上面的算法在计算机上均已实现,并且对输
入的任意正则表达式,都能输出对应该正则表达
式的DFA.因此,如果要实现某一离散信息处理
过程,可先写出其正则表达式,然后利用上述算法
求出它的DFA模型,最后设计一个程序,或设计
一个电路模拟该DFA.
参 考 文 献
1 HopcroftJE,UllmanJD.Introductiontoautomatatheory,
languagesandcomputation.Massachusetts:Addison-Wesley,
1979
2 LeeSC.Modernswitchingtheoryanddigitaldesign.London:
Prentice-Hall,1978
3 MannaZ.Mathematicaltheoryofcomputation.NewYork:
McGraw-Hill,1974
4 孙怀民.离散数学.北京:北京航空航天大学出版社,1990
AlgorithmforConstructingtheSimplifiedDFAofRegularExpressions
TanFengqin
(BeijingUniversityofAeronauticsandAstronautics,Dept.ofComputerScienceandEngineering)
Abstract AnalgorithmforconstructingthesimplifiedDFA(DeterministicFiniteAutomaton)is
introduced,whichisequivalenttoagivenregularexpression.ThefirststepconstructsanNFA(Non-
deterministicFiniteAutomaton)equivalenttotheregularexpression,wheretheoperationforcon-
structingfiniteautomatawithε-movesisomitted.ThenthesimplifiedDFAequivalenttotheNFAis
constructedbyusingstatetransitiontrees.Thealgorithmbasbeenrealizedbycomputerprogram-
ming,andforanyinputregularexpression,asimplifiedDFAequivalenttotheregularexpressionis
produced.Thealgorithmcanbeappliedinthedesignandanalysisofthesystemwithdiscreteinputs
andoutputs.
Keywords finiteautomata;states;statefunctions;recognition;statediagrams
894 北 京 航 空 航 天 大 学 学 报 1998年
浙公网安备 33021202002483