正则表达式与有限自动机的关系 右线性语言与有限自动机的关.ppt

《正则表达式与有限自动机的关系 右线性语言与有限自动机的关.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、正则表达式与有限自动机的关系右线性语言与有限自动机的关系右线性语言的性质(part1)第四讲1CollegeofComputerScience&Technology,BUPT3.7正则表达式与有限自动机的关系结论:有限自动机、右（左）线性文法、正则表达式都定义了同一种语言--正则语言.证明策略-NFANFADFARERE(RegularExpression)---正则表达式2CollegeofComputerScience&Technology,BUPT从DFA构造等价的正则表达式（状态消去法）思路:(1)扩展自动机的概念，允许正则表达式作为转移弧

2、的标记.这样，就有可能在消去某一中间状态时，保证自动机能够接受的字符串集合保持不变.(2)在消去某一中间状态时，与其相关的转移弧也将同时消去，所造成的影响将通过修改从每一个前趋状态到每一个后继状态的转移弧标记来弥补.以下分别介绍中间状态的消去与正则表达式构造过程.3CollegeofComputerScience&Technology,BUPT从DFA构造等价的正则表达式（中间状态的消去）xyr1r2xzr1yr2代之以：xyr1+r2xyr2r1代之以：xyr1*xzyr1代之以：4CollegeofComputerScience&Techno

3、logy,BUPT从DFA构造等价的正则表达式（中间状态的消去）q1qkp1pmP1PmQkQ1R11R1mRkmRk1R11+Q1S*P1R1m+Q1S*PmRkm+QkS*PmRk1+QkS*P1q1p1qkpm消去s5CollegeofComputerScience&Technology,BUPT从DFA构造等价的正则表达式（状态消去法）步骤:(1)对每一终态q，依次消去除q和初态q0之外的其它状态;(2)若qq0，最终可得到一般形式如下左图两状态自动机，该自动机对应的正则表达式可表示为(R+SU*T)*SU*.(3)若q=

4、q0，最终可得到如下右图的自动机，它对应的正则表达式可以表示为R*.(4)最终的正则表达式为每一终态对应的正则表达式之和（并）.6CollegeofComputerScience&Technology,BUPT状态消去法举例对于终态C对于终态D等价的正则表达式(0+1)*1(0+1)+(0+1)*1(0+1)(0+1)7CollegeofComputerScience&Technology,BUPT状态消去法举例01342567abaabbab012567a+ba+baabb0257(a+b)*(a+b)*aa+bb07(a+b)*(

5、aa+bb)(a+b)*8CollegeofComputerScience&Technology,BUPT定理:L是正则表达式R表示的语言,则存在一个-NFAE,满足L(E)=L(R)=L.证明:构造性证明.可以通过结构归纳法证明从R可以构造出与其等价的，满足如下条件的-NFA：(1)恰好一个终态;(2)没有弧进入初态；(3)没有弧离开终态；从正则表达式构造等价的-NFA9CollegeofComputerScience&Technology,BUPT基础:从正则表达式构造等价的-NFA（归纳构造过程）1对于，构造为3对于a，构造为a2对

6、于，构造为10CollegeofComputerScience&Technology,BUPT归纳:从正则表达式构造等价的-NFA（归纳构造过程）1对于R+S，构造为11CollegeofComputerScience&Technology,BUPT归纳:从正则表达式构造等价的-NFA（归纳构造过程）2对于RS，构造为3对于R*，构造为12CollegeofComputerScience&Technology,BUPT举例:设正则表达式1*0(0+1)*,构造等价的-NFA.从正则表达式构造等价的-NFA0+11*

7、13CollegeofComputerScience&Technology,BUPT从正则表达式构造等价的-NFA(0+1)*1*0(0+1)*14CollegeofComputerScience&Technology,BUPT3.8右线性语言与有限自动机至此，我们已学到正则集有三种定义方式，且这三种方式等价：正则集是含有{ε}，φ，{a}以及在并、连接和*运算下封闭的语言由正规表达式定义的集合是正则集。由右线性文法生成的语言是正则集。此外，还有第四种方式：将正则集作为由有限自动机定义的集合。即正

8、则集(右线性语言)<＝>有限自动机15CollegeofComputerScience&Technology