《《编译原理》课程简介 (15).pdf》由会员分享，可在线阅读，更多相关《《编译原理》课程简介 (15).pdf（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、编译原理 C O M P I L A T I O N P RIN C IP LE第三章 词法分析3.3 正规式与有限自动机3.3 正规式与有限自动机一、基本概念二、确定有穷状态自动机（DFA）三、非确定有穷状态自动机（NFA）四、正规式和有限自动机的等价性五、DFA的化简3.3 正规式与有限自动机v1上NFA M所能识别的字的全体是上的一个正规集n证明：设转换图中每条弧上可用一个正规式作标记，让NFA M的转换图中加进两节点X和Y，形成新的NFA M，从X画弧指向原NFA M的所有初态，从原NFA M的所有终态画弧指向Y，显然L(M)=L(M)n然后，对NFA M消结，直至只剩下X、Y两个结点
2、为止，符上标记为一正规式。n所以，NFA M识别的为一正规式；NFA M识别的是一正规集。四、正规式和有限自动机的等价性Xu=uu=u3.3 正规式与有限自动机:消结规则为代之以代之以代之以3.3 正规式与有限自动机解：消结点例13.3 正规式与有限自动机解：消结点例23.3 正规式与有限自动机v2.对于上的每个正规集V，存在一个上的DFA M，使得V=L(M)。n证明：第一步，用替代办法构造一个NFA M，使V=L(M)，因为正规集V可用正规式u来描述，而u由一系列单个字符连接而成，故可用下述方法分解之：四、正规式和有限自动机的等价性SZe1e2SZe1e2SZe1|e2SZeSZ SZe1
3、e2e3.3 正规式与有限自动机 正则表达式(A|B)A|B|0|1的转换系统的构造过程如下：例SZ(A|B)A|B|0|1SZ(A|B)A|B|0|1SZAB A|B|0|1SZAB 10AB3.3 正规式与有限自动机v2.对于上的每个正规集V，存在一个上的DFA M，使得V=L(M)。n具体方法：构造如下转换图：逐步分解，便可得到一个NFA M，有L(u)=V=L(M)。n第二步，把NFA M确定化为DFA M，得证。四、正规式和有限自动机的等价性3.3 正规式与有限自动机概念概念1 1假设I是NFA M的状态集的一个子集，我们定义-CLOSURE(I)为（I的-闭包）。（1）若SI，则S
4、-CLOSURE(I)（2）若SI，则从s出发经过任意条弧而达到的状态s，有s-CLOSURE(I)例1若I=1,3，则-CLOSURE(I)=1,3,2,83.3 正规式与有限自动机 同例1 DFA，Ia=5,6,2概念概念2 2 假定I是M的状态子集，a是中的字符，定义Ia=-CLOSURE(J),其中J是I中任意状态出发（跳过前面任意多条弧），经过一条a弧而能达到的状态结的全体。例2n 利用概念1和概念2，便可把NFA确定化。3.3 正规式与有限自动机n令=a1,a2,，am，构造一张如下的表，此表第0列为状态子集I，第1至m列分别为状态子集Ia1 ，Ia2，.，Iam ，设第一行第0列
5、为-CLOSURE(X),，其中X为NFA M的初态，求出第一个的Ia1 ，Ia2，.，Iam，如果某个Iai(i=1,m)未曾在第0列中列出，则把Iai补入状态子集集合I中，即列于第0列新的一行。n重复上述各步，直至所有行的Iai(i=1,m)均在第0列I中出现过为止。这种循环必将在有限步内中止。（因为S是有限状态集，所以S中状态的组合数也是有限的）3.3 正规式与有限自动机n显然，这张表可以看成一个状态转换表，也就是说可把I中每个子集看成一个状态，而状态转换表唯一地刻划了一个DFA M，其初态为该表的第1行第0列，含有原NFA M终态的子集为新的终态。（证毕）n推论：一个子集是正规的，当且
6、仅当它可由一个DFA（或NFA）所识别。3.3 正规式与有限自动机 正规式(a|b)*(aa|bb)(a|b)*对应的NFA如下图所示。其中X为初态，Y为终态。按照上述证明过程构造出来的状态转换矩阵见表例1bb3.3 正规式与有限自动机IIaIbX,5,15,3,15,4,15,3,15,3,1,2,6,Y5,4,15,4,15,3,15,4,1,2,6,Y5,3,1,2,6,Y5,3,1,2,6,Y5,4,1,6,Y5,4,1,6,Y5,3,1,6,Y5,4,1,2,6,Y5,4,1,2,6,Y5,3,1,6,Y5,4,1,2,6,Y5,3,1,6,Y5,3,1,2,6,Y5,4,1,6,Y例对应于上例中正规式的状态转换矩阵3.3 正规式与有限自动机sab0121322153344655656340213465aaaaaabbbbbbba3.3 正规式与有限自动机18 设计一个DFA M，它识别二进制偶数（不以0开头的无符号数）例例2 2n解：1写出正规式 1（1|0）*0 3.确定化为DFA M2画出NFA M 细化为：NAMENAMEI I0 0I I1 1A11,Y1,Y1,Y1113.3 正规式与有限自动机或：l确定为DFA是怎样的？3.3 正规式与有限自动机20l确定为DFA：l同学们，两种方法得出了不同的DFA，他们是否相等呢？|编译原理谢 谢Thanks