形式语言与自动机5教学讲解教案.pdf

《形式语言与自动机5教学讲解教案.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、FL&A第五讲有限状态自动机正规表达式FL&A有限状态自动机正规表达式有限自动机与正规表达式的关系几个转换算法的复杂度（选讲）FL&A有限自动机与正规表达式的关系结论:有限自动机所表示的语言是正规语言证明策略-NFANFAREDFAFL&A有限自动机与正规表达式的关系从正规表达式构造等价的-NFA定理:L是正规表达式R表示的语言,则存在一个-NFAE,满足L(E)=L(R)=L.证明:构造性证明.可以通过结构归纳法证明从R可以构造出与其等价的，满足如下条件的-NFA：(1)恰好一个终态;(2)没有弧进入初态；(3)没有弧离开终态；•FL&A

2、有限自动机与正规表达式的关系归纳构造过程(从正规表达式构造等价的-NFA)（Thompson构造法）基础:1对于，构造为2对于，构造为3对于a，构造为aFL&A有限自动机与正规表达式的关系归纳构造过程(从正规表达式构造等价的-NFA)（Thompson构造法）R归纳:1对于R+S，构造为SRSFL&A有限自动机与正规表达式的关系归纳构造过程(从正规表达式构造等价的-NFA)（Thompson构造法）R归纳:S2对于RS，构造为RS3对于R*，构造为RFL&A有限自动机与正规表达式的关系举例(从正规表达式构造等价的-NFA

3、)设正规表达式1*0(0+1)*,构造等价的-NFA.11*00+11FL&A有限自动机与正规表达式的关系举例(从正规表达式构造等价的-NFA)0(0+1)*11*0(0+1)*1001FL&A有限自动机与正规表达式的关系从DFA构造等价的正规表达式定理:L是某个DFAD的语言,则存在一个正规表达式R,满足L(R)=L(D)=L.证明:构造性证明.以下是两种构造方法(1)路径叠代法（Kleene构造法）;(2)状态消去法•FL&A有限自动机与正规表达式的关系路径叠代法（从DFA构造等价的正规表达

4、式）步骤:(1)将DFAD的状态集用{1,2,…,n}表达，且初态为1;(2)对所有1i,jn,0kn，叠代计算R(k)ij；这里,R(k)为表示如下语言的正规表达式：ijwL(R(k))iff从i到j有一条标记为w的ij路径,且这条路径上除i和j之外的所有状态的编号不大于k(3)通过(2)的叠代过程，最终可计算出R(n)（i,j=1,2,…,n）;ij(4)将所有R(n)（j为任一终态）相“”1jFL&A有限自动机与正规表达式的关系计算R(k)的叠代过程ij基础:k=0Case1ij若不存在从i到j的弧，则R(0)=；ij若仅存在一条从i到j

5、的弧，且标记为a，则R(0)=a；ij若存在多条从i到j的弧，且标记为a,a,…,a，12m则R(0)=aa…a；ij12mCase2i=j若不存在从i到自身的圈，则R(0)=；ij若存在一个从i到自身的圈且标记为a，则R(0)=a；ij若存在多个从i到自身的圈，且标记为a,a,…,a，12m则R(0)=aa…a；ij12mFL&A有限自动机与正规表达式的关系计算R(k)的叠代过程ij归纳:假设R(k-1)（i,j=1,2,…,n）已经求出.则叠代ij公式为R(k)=R(k-1)R(k-1)(R(k-1))*R(k-1)ijijikkkk

6、j分析:考虑从i到j的路径（除i和j之外的所有状态的编号不大于k）Case1路径不经过k.此时，标记该路径的字符串属于L(R(k-1));ijCase2路径经过k至少一次.此时，标记该路径的字符串属于L(R(k-1)(R(k-1))*R(k-1)).如下图所示：ikkkkj...ikkkjR(k-1)(R(k-1))*R(k-1)ikkkkjFL&A有限自动机与正规表达式的关系路径叠代法举例10,1Start012R(0)111R(0)012R(0)21R(0)0122FL&A有限自动机与正规表达式的关系路径叠代法举例1R(0)1110,1Sta

7、rt0R(0)01212R(0)21R(0)0122直接替换化简R(1)1(1)(1)*(1)1*11R(1)0(1)(1)*01*012R(1)(1)*(1)21R(1)01(1)*00122R(1)=R(0)R(0)(R(0))*R(0)ijiji1111jFL&A有限自动机与正规表达式的关系路径叠代法举例1R(1)1*110,1R(1)1*0Start01212R(1)21R(1)0122直接替换化简R(2)1*1*0(01)*1*11R(2)1*01*0(