1、2022-6-81Principle of Compiling郭郭 一一 晶晶 厦门大学嘉庚学院厦门大学嘉庚学院 2022-6-82l2.4.1由由正规式正规式构造等价的构造等价的NFA Ml2.4.2 NFA M的的确定化确定化l2.4.3 DFA M的的化简化简l2.4.4 正规式到有限自动机构造正规式到有限自动机构造示例示例l2.4.5 从从NFA M到正规表达式的到正规表达式的转换转换2022-6-83有有限限自动机和正规表达式的自动机和正规表达式的等价性等价性：l1.对于对于上的一个上的一个NFA M，可以构造一，可以构造一个个上的上的正规式正规式R R, ,使得使得L(R)=L(M
2、)。l2 2. .对于对于上的一个上的一个正规式正规式R，可以构造一，可以构造一个个上的上的NFA M，使得使得L(M)=L(R)。l注意注意：与某一NFA等价的DFA不一定唯一。2022-6-842.4 正规式到有限自动机的构造正规式到有限自动机的构造2.4.1 由由正规式正规式构造等价的构造等价的NFA M 由正规式构造等价的NFA M的方法(Thompson构造法)： (1) 将正规式R表示为拓广转换图。X2 YR2022-6-85(2) 采用下述三条转换规则构造NFA M。sisisjr1 | r21.r1r2ee2.3.sjsjsisir1 r2sisi*r1r1r1r2sjsjsj
3、sksk2022-6-86 对于正规式R,首先将其表示为拓广转换图,其中X为初态,Y为终态,然后逐步运用三条转换规则不断加入新结点,直至每条有向边上仅标识的一个字母或为止,至此 NFA M构造完成。 例例2.6 构造 b*(d|ad)(b|ab)+对应的NFA。解: 首先用R+=RR*把正规式改造为 b*(d|ad) (b|ab) (b|ab)* 然后构造其NFA M，如下图所示：2022-6-87b*(d|ad)(b|ab)(b|ab)*XY(b|ab)*d|adb*b|ababadbdb|abb41235bX41d26bb3578adbaabXX132YYY2022-6-88lThomps
4、on方法构造的方法构造的NFA有有下列下列性质性质：l只有一个开始状态和一个接受状态，接受状态没有向外的转换。l 的转换规则可不可以改为？*r1sisjeer1例：(11+)*2022-6-892.4.2 NFA M的的确定化确定化子集构造法子集构造法(Subset Construction)首先首先定义定义FA M的任一状态子集 I 的 e_CLOSURE(I)： (1)若siI, 则sie_CLOSURE(I)； (2)若siI, 则从 si 出发经过e所能到达的 状态 sj 属于e_CLOSURE(I)。其次其次定义定义Ia： 对FA M的任一状态子集 I , 若a是中的一个字符字符，则
5、定义 Ia=e_CLOSURE(J)， 其中 J 是从 I 中某一状态出发经过a所能到达的所有状态的集合。 Jmove(I,a)2022-6-810例例2.7 对下图,取 I=e_CLOSURE1=1,2, 求从状态I出发经一条有向边a所能 到达的状态集J和e_CLOSURE(J)。a1524ae e6378e ee eae ee e J=5, 3, 4 e_CLOSURE(J)=5, 6, 2, 3, 8, 4, 72022-6-811用子集法对用子集法对NFA确定化的方法确定化的方法：(1)构造一张转换表, 该表的第1列为状态 子集I, 不同输入符a 对应表中一列Ia。(2)表的首行首列为
6、e_CLOSURE(s0)。(3)根据首行首列中的状态集, 为每个输 入符a求其Ia并记入相应的Ia列中。 若此Ia不同于第1列已存在的所有状态 子集, 则将其顺序列入空行中的第1列。(4)重复(3)直至对每个I及a均已求得Ia, 且 无新的状态子集Ia加入第1列为止。 (5)重命名第1列的每个状态集, 所得状态 转换矩阵即为与NFA M等价的DFA M。2022-6-812例例2.8 正规式(a|b)*(aa|bb)(a|b)*的NFA M如下: 试将其确定化为DFA M。34251X6eeabababeeab2 Y2022-6-813解: 用子集法将上述NFA M 确定化为 IIaIbX,
7、1,21,2,31,2,41,2,31,2,3,5,6,Y1,2,41,2,41,2,31,2,4,5,6,Y1,2,3,5,6,Y1,2,3,5,6,Y1,2,4,6,Y1,2,4,5,6,Y1,2,3,6,Y1,2,4,5,6,Y1,2,4,6,Y1,2,3,6,Y1,2,4,5,6,Y1,2,3,6,Y1,2,3,5,6,Y1,2,4,6,Y2022-6-814Sab012132214335464564635重命名为:2022-6-815a2 32 52 42 6120abbaababbaabb于是得到对应的DFA如下：2022-6-816l注意：如果DFA的某个状态至少包含NFA的一个
8、接受状态，那么，这个状态是DFA的一个接受状态。lDFA的一个状态是NFA的一个状态集合状态集合。l读了输入a1a2an后，NFA能到达的所有状态：s1, s2, , sk，则DFA到达状态s1, s2, , sk。2022-6-817l算法描述：1 开始，假定所构造的子集族为C，令e-closure(K0)为C中唯一成员，并且它是未被标记的。2 while （C中存在尚未被标记的子集T）do 标记T； for 每个输入字母a do U:= e-closure(move(T,a)； if U不在C中 then 将U作为未标记的子集加在C中 2022-6-8182.4.3 DFA M的的化简化简
9、 (DFA Minimization) NFA确定化所得的DFA可能含有多余的状态, 需化简。所谓DFA M的化简的化简，是指寻找一个状态数比M少的DFA M，使得L(M) = L(M)。 化简后的DFA M 满足下述条件： (1) 无多余状态 (死状态)； (2) 状态集中无相互等价（不可区别）的状态。 2022-6-819 两个状态相互等价两个状态相互等价是指: 对于给定的DFA M, 假定状态s1,s2S且s1s2, 若从s1出发能识别字符串而停于终态, 从s2出发也能识别而停于终态; 反之, 若从s2出发能识别而停于终态, 从s1出发也能识别而停于终态, 则称s1和s2等价等价, 否则
10、称s1和s2是可区分可区分的。 假定状态s1,s2S且s1s2, 若s1和s2通过同一字符(串)到达了可区分的状态，则s1和s2也是可区分的。 2022-6-820DFA M的状态最小化过程状态最小化过程： 将M的状态集分割成一些不相交的子集，使得任意两个不同子集的状态是可区分的，而同一子集中的任意两个状态都是等价的。最后, 从每个子集中选出一种状态，同时消去其它等价状态，就得到最简的DFA M且L(M) = L(M)。 2022-6-821DFA M的化简方法的化简方法 (Hopcroft算法) ：(1)首先将DFA M的状态集S中的终态与非终态分开,形成两个子集,得到基本划分。(2)对当前
11、已划分出的I(1),I(2),I(m)子集, 看每每个个I是否能进一步划分。对某个I( i )= s1,s2,sk, 若存在输入字符a使得Ia(i)不不全包含全包含在当前划分的某个子集I(j)中, 即跨越两个子集, 则将I(i)一分为二(下页)。(3)重复(2), 直到每个子集均不能再分不能再分。 不能再分是指子集要么仅有一个状态，要么有多个状态但这些状态不可区分。2022-6-822(a)无需划分(b)需划分s4s3s3s1s2s1s2aaaas42022-6-823如何进行子集的划分呢如何进行子集的划分呢？ 假定当前子集I(i)=s1,s2,其中s1和s2经过有向边a分别到达状态t1和t2
12、, 而t1和t2分属于当前已划出的两个不同子集I(j)和I(k),则应将I(i)分为两部分： I(i1)= s | sI(i)且s经有向边a到达t1 I(i2)= I(i) I(i1) (由于t1和t2是可区分的， 因此I(i1)中的状态与I(i2)中的状态可区分)2022-6-824 划分结束后, 子集个数不再增加, 从每个子集中选一个状态形成新的DFA。 例如， I(i)=s1, s2, s3 若挑选s1作为I(i)的代表，则原来指向s2和s3的有向边均改为指向新DFA中的s1。 若I(i)中含原来的初态，则s1为新初态； 若I(i)中含原来的终态，则s1为新终态。2022-6-825例例
13、2.9 化简由例2.8得到的DFA。2 32 52 42 6120abbaababbaabbab解: (1)先将状态集S=0,1,2,3,4,5,6划分为 终态集3,4,5,6和非终态集0,1,2。 (2)考察0,1,2a:因0,2,1a=1,3不属于 3,4,5,6和0,1,2,故将0,1,2划分为 0,2和1。2022-6-826(3)考察0,2b:因0,2b=2,4,不属于已划分 出的某个子集, 故0,2划分为0和2。(4)考察3,4,5,6a： 3,4,5,6a=3,6,属于3,4,5,6,故不划分。(5)考察3,4,5,6b： 3,4,5,6b=4,5,属于3,4,5,6,故不划分。
14、(6)按顺序把状态子集0,1,2,3,4,5,6 重命名为0,1,2,3, 得到化简后的DFA M:2022-6-827Sab0121322133331203 3aabbbaab2022-6-828l结论接受L的最小状态有穷自动机，若不计同构则是唯一的。l另一种等价的构造方法：填表算法，参考本节最后的附加ppt。2022-6-8292.4.4 2.4.4 正规式到有限自动机构造正规式到有限自动机构造示例示例例例2.10 试用DFA的等价性证明正规式 (a|b)*与(a*b*)*等价。解: (1)正规式(a|b)*对应的NFA如下：X12 Yaeeb2022-6-830用子集法确定化得如下转换表
15、:IIaIbX,1,Y1,Y1,Y1,Y1,Y1,YSab011111重命名转换表得:2022-6-831于是得到DFA 如下:0ab1ab0ba化简: 因0,1a=1, 故不划分。 因0,1b=1, 故不划分。因此, 最简DFA如下:2022-6-832IIaIbX,1,2,3,Y 2,3,1,Y 2,3,1,Y2,3,1,Y2,3,1,Y2,3,1,YSab011111重命名得状态转换矩阵:由于(a|b)*和(a*b*)*对应的状态转换矩阵相同, 故二者等价。 (2) (a*b*)*对应的NFA如图2-20所示, 用子集法将NFA确定化得下述转换表:2022-6-833例例2.11 C语言
16、可接受的合法文件名为 device: name.extension 其中device:和.extension可省。假定device, name和extension都是字母串, 长度不限但至少为1, 试画出识别文件名的DFA M。 解: 所求正规式为(cc*:|e)cc*(.cc*|e) 相应的NFA M如下图所示：X2Y1234c : ccccc2022-6-834首先进行预处理。然后用子集法确定化、重命名。Sc:.01-112324-35-44-355-IIcI:I.X,21,3,Y-1,3,Y1,3,Y2423,Y-4Y-3,Y3,Y-YY-2022-6-8352 4022 132 5cc
17、：cccc于是得到DFA如下：最后对DFA化简化简,化简后仍为上图。2022-6-836例例2.12 某高级程序语言无符号数的正规式 为 digit+(.digit+)?(e (+|)?digit+)? 其中digit表示数字, ()?表示()中内容 可有可无, 试给出其DFA M。 解: 用d代表digit，其NFA如下图所示：X2 Y1234d5eddddedd+2022-6-837IIIdI.IeX1,Y1,Y1,Y24,523,Y4,55Y3,Y3,Y4,55YYYS d.e0 1 1 1232 43564 435 66 6用子集法将NFA M确定化,然后重命名。2022-6-8380
18、32 1522 42 6ddedddedd于是得到下图所示的DFA M :由状态转换矩阵可见, 状态5和6面对输入符号的下一状态相同, 但状态5为非终态, 状态6为终态, 故上述DFA已为最简。2022-6-839例例2.13 构造一DFA, 它接收=a,b上所有 满足下述条件的字符串: 该字符串中的 每个a都有至少一个b直接跟在其右边。解: = a,b, 所求正规式为b*(abb*)*。 相应的NFA M如下图所示:X2 Y12eeebabb*X2Y1eeeb342aebb2022-6-840IIaIbX,1,2,Y31,2,Y34,2,Y1,2,Y31,2,Y4,2,Y34,2,YSab0
19、1213212313用子集法将NFA M确定化, 然后重命名。2022-6-8412 02 32 21abaabbb于是得到DFA M 如下:2022-6-8422 0bb1a用DFA M的化简方法得到最终划分： 0,2,3, 1 重命名后得到化简的DFA M如下: 2022-6-843l正规表达式和NFA等价l任何一个正规表达式表示的语言，存在一个NFA识别（Thompson构造法构造法）l任何一个NFA识别的语言，可以表示为一个正规表达式拓广状态转换图的概念，转移符号可以用一个正规表达式标记2022-6-844方法方法： l 1. 在 M的状态转换图上增加状态X, Y，从X到初始状态q0
20、用e弧连接，从M的所有终态到Y用e弧连接，得到的新的NFA为M，它只有一个初始状态X和一个终止状态 Y。l2. 反复应用以下三条规则，消去 e-NFA M中的状态结点和弧，直至只剩下状态结点X、Y及连接二者的弧。在消去的过程中，用正规表达式标记弧。2022-6-845从FA M到正规式的转换规则如下:sisjr1 | r21.2.3.sjsir1 r2*sjsir1r1r2sisjsir1r2sjskeesir1sjsk2022-6-846l3. 连接X、Y结点边的标记r 即为所求的正规表达式：XYrstart2022-6-847iqdaeqcbjqdae*iqdce*bae*jqbce*20
21、22-6-848r1*r2( r4|r3r1*r2)*fq2r3r1r0q4r2022-6-84915432rsvwtu(1)15432rsvwt | u(2)1254r(t | u)*vs(t | u)*ws(t | u)*vr(t | u)*w(3)消除状态32022-6-850q0q2q11221202022-6-851q0q2q1122120qefeee2022-6-852q0q220qefee2|11*211*2022-6-853q00qef(11*)|(2|11*2)2*)e2022-6-854qfe|0*|0*(11*)|(2|11*2)2*)化简得：0*1*2*2022-6-8
22、55312011110000start偶偶0偶偶1奇奇0奇奇1奇奇0偶偶1偶偶0奇奇12022-6-8563201110110100start002022-6-8573011|0010|0101|10start00|112022-6-858011|00(10|01)(00|11)*(01|10)startqf( (00|11) | (10|01)(00|11)*(01|10) )*即：start2022-6-859lP31 l2.4，2.7(画出对应的NFA即可)，2.8，2.102022-6-860l状态的等价性p和q等价：l若两个状态不等价，则称二者是可区分的。pqwworpqww2022
23、-6-861fbcdeaghgfedcb1. Initialize table entries: Unmarked, empty listAEBFCGDH00000000111111112022-6-862fbcdeaghgfedcb2. Mark pairs of final & nonfinal statesAEBFCGDH00000000111111112022-6-863fbcdeaghgfedcb3. For each unmarked pair & symbol, d(b,0) ? d(a,0)d(b,1) ? d(a,1)AEBFCGDH0000000011111111g ? b
24、c ? fMaybe.No!2022-6-864fbcdeaghgfedcb3. For each unmarked pair & symbol, d(d,0) ? d(a,0)d(d,1) ? d(a,1)AEBFCGDH00000000111111112022-6-865fbcdeaghgfedcbd(e,0) ? d(a,0)d(e,1) ? d(a,1)3. For each unmarked pair & symbol, AEBFCGDH0000000011111111h ? bf ? fMaybe.Yes.2022-6-866fbcdeaghgfedcb(a,e)(g,a)(g,a
25、)3. For each unmarked pair & symbol, AEBFCGDH00000000111111112022-6-867fbcdeaghgfedcbaebfcgdh0000000011111111(a,e)(g,a)(g,a)Need to mark.So, mark (g,a) also.3. For each unmarked pair & symbol, 2022-6-868fbcdeaghgfedcb(g,a)(a,e)3. For each unmarked pair & symbol, AEBFCGDH00000000111111112022-6-869fbcdeaghgfedcb4. Coalesce unmarked pairs of states.(a,e)a eb hd fAEBFCGDH0000000011111111aebhdfcg00000111112022-6-870fbcdeaghgfedcb(a,e)None.AEBFCGDH0000000011111111aebhdfcg00000111115. Delete unreachable states.2022-6-871
