编 译 原 理 Principle of Compiling郭一晶厦门大学嘉庚学院 10/14/2022 12.4 正规表达式到有限自动机的构造l 2.4.1由正规式构造等价的NFAMl 2.4.2NFAM的确定化l 2.4.3DFAM的化简l 2.4.4正规式到有限自动机构造示例l 2.4.5从NFAM到正规表达式的转换10/14/2022 2有限自动机和正规表达式的等价性：l 1.对于上的一个NFAM，可以构造一个上的正规式R,使得L(R)=L(M)。l2.对于上的一个正规式R，可以构造一个上的NFAM，使得L(M)=L(R)。l注意：与某一NFA 等价的DFA 不一定唯一。10/14/2022 32.4 正规式到有限自动机的构造2.4.1由正规式构造等价的NFAM由正规式构造等价的NFAM 的方法(Thompson 构造法) ：(1) 将正规式R 表示为拓广转换图。X 2 YR10/14/2022 4(2) 采用下述三条转换规则构造NFA M 。sisisjr1|r21.r1r2 2.3.sjsjsisir1r2sisi*r1r1r1r2sjsjsjsksk10/14/2022
