编译原理3.3.5-RE和FA转换.ppt

《编译原理3.3.5-RE和FA转换.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章词法分析3.1对于词法分析器的要求3.2词法分析器的设计3.3正规表达式和自动机3.4词法分析器的自动产生3.3正规表达式和自动机3.3.1正规式和正规集3.3.2确定有限自动机3.3.3非确定有限自动机3.3.4正规文法与有限自动机的等价性3.3.5正规式与有限自动机的等价性3.3.6确定有限自动机的化简3.3.5RE与FA的等价性1.对于∑上的一个NFAM，可以构造一个∑上的正规式R,使得L(R)=L(M)2.对于∑上的一个正规式R，可以构造一个∑上的NFAM，使得L(M)=L(R)1.从Σ上的一个NFAM构造等价的正规式RFA－>RE首先把状态转换图的概念拓

2、广，令每条弧可用一个正规式作标记第一步：在状态转换图上加进两结点，x结点和y结点从x结点用ε弧连接到M的所有初态结点从M的所有终态结点用ε弧连接到y结点将NFA转换成具有唯一初态和唯一终态的NFA第二步：逐步消去所有结点，直至只剩下x和y结点V1V2V2V112313V2V1V1V21213V1V2*V313V2V3V1123结点消去规则补充例：FA－>REbbaa321aaa,b0a,b4a,bR=(a

3、b)*(aa

4、bb)(a

5、b)*解题过程见黑板可以把NFA确定化最小化后在转化成等价的正规式2.从Σ上的一个正规式R构造一个等价的NFAMRE－>FAq0qf正规式

6、Ø正规式εq0正规式aaq0qf{}{ε}{a}r=r1

7、r2M1q1f1q0f0M2q2f2L(Mi)=L(ri)εεεεM中有一条从q0到f0通路w,当且仅当在M1中由一条从q1到f1的通路w,或者在M2中由一条从q2到f2的通路wM1M2r=r1r2q1f2f1q2εL(Mi)=L(ri)r=r1*M1q1f1q0L(M1)=L(r1)εεεεf0补充例:为R=(a

8、b)*abb构造等价NFA解题过程见黑板V2V1V2*V3V3V112313R=(a

9、b)*abbxijklyababbεε例3.5p56