川师编译原理课件4.ppt

4.3.3 ＮFA到DFA的转换 ε闭包：ε-closure(I)表示状态集I中任何状态A经任意条ε弧而能到达的状态集。 状态集I的a弧转换，表示为=move(I,a), J是所有那些从I中任何状态A经一条a弧而到达的状态全体 令Ia=ε-closure(J) 例：取I={S,1},则ε-closure(I)＝{S,1,2}, J=move(I,0)={1},I0=ε-closure(J)={1,2} 用造表法将NFA确定化过程如下： (0)表的第0行和第0列作标识行列。 (1)将ε-closure(I)作为表中第1行第1列。 (2)假定?={a1,a2,...an},设第i行第一列已确定状态集为I,则置该行第i列为Iai,如Iai未曾在任何行第一列出现过，则将Iai加入后面空行第一列。 (3)反复重复第(2)步，直至无新状态出现为止。 (4)重新命名新状态。 例：将图示NFA确定化 I0(ε-closure(move(Ti,o)) I1 T1 {S,1,2} {1,3,2} {1,4,2} T2 {1,3,2} {1,3,5,2,6,Z} {1,4,2} T3 {1,4,2} {1,3,2} {1,4,5,2,6,Z} T4 {1,3,5,2,6,Z} {1,5,3,2,6,Z} {1,4,6,2,Z} T5 {1,4,5,2,6,Z} {1,3,6,2,Z} {1,5,4,2,6,Z} T6 {1,4,6,2,Z} {1,3,6,2,Z} {1,5,4,2,6,Z} T7 {1,3,6,2,Z} {1,5,3,2,6,Z} {1,4,6,2,Z} 0 1 1 (T1) ２ ３ 2 (T2) ４ ３ 3 (T3) ２ ５ 4 (T4) ４ ６ 5 (T5) ７ ５ 6 (T6) ７ ５ 7 (T7) ４ ６ 4.3.4 DFA的化简 一个DFA是化简(最小化)了的，即是说，它没有多余状态且其状态中没有相互等价的。 多余状态是指从自动机的开始状态出发，任何输入串也不可达的状态 在DFA中，两个状态s和t等价的条件是： (1)一致性条件：状态s和t必须同时为可接受态和不可接受态。 (2)蔓延性条件：对于所有输入符号，状态s和t必须转换到等价的状态里。 对DFA最小化的本质： 消除多余状态、合并等价状态。 DFA最小化过程： 用分割法将不含多余状态的DFA分成一些不相交的子集，使得任何两个不同的子集中的状态都是可区别的，而相同子集中状态是等价的。 分割时，首先将DFA状态分成终态子集和非终态子集，再根据输出弧所达到状态的性质逐步细分。 例：对图示DFA最小化。 解：P0={{1,2,3},{4,5,6,7}} 根据各子集输出弧0和1所达到状态是否为终态，划分为： P1={{1}, {2}, {3}，{4,5,6,7}} 最小化后DFA为右下图。 化简前的DFA 化简后的DFA 4.4 正规式和NFA的等价性 对于?上的每个NFA M，可以构造一个相应的?上的正规式R，使得L(R)=L(M) 对于?上的每个正规式R，可以构造一个相应的?上的NFA M，使得L(R)=L(M) 一、为NFA M构造相应的正规式R 首先引入两个新结点x,y;x经ε弧到所有初态，所有终态经ε弧到y； 再用如下消解规则消去除x,y外的所有结点，最后x,y间弧上的标记串就是所求正规式。 例：给出与图示NFA M等价的正规式R 解：R=(0|1)*(00|11)(0|1)* 二、由正规式R构造相应的NFA N 其过程与上述过程相反。 用如下构造规则构造NFA ： 对 R=ε构造: - ε R=a构造: - a R=st构造: - N(s) N(t) （其中s、t 分别为正规式） X Y X Y X Y R=s|t构造: ε N(s) ε - ε N(t) ε R=s*构造: ε - ε N(s) ε ε X Y X Y 例：为R=(a|b)*abb构造NFA N，使L(R)=L(N)。 ε 解： ε a ε ε b ε