Chapt3解读.ppt

具体做法: 对M的状态集进行划分 首先，把S划分为终态和非终态两个子集，形成基本划分?。 假定到某个时候，?已含m个子集，记为?={I(1)，I(2)，?，I(m)}，检查?中的每个子集看是否能进一步划分: 对某个I(i)，令I(i)={s1,s2, ?,sk}，若存在一个输入字符a使得Ia(i) 不会包含在现行?的某个子集I(j)中，则至少应把I(i)分为两个部分。 例如，假定状态s1和s2经a弧分别到达t1和t2，而t1和t2属于现行?中的两个不同子集，说明有一个字?， t1读出?后到达终态，而t2读出?后不能到达终态，或者反之，那么对于字a? ， s1读出a?后到达终态，而s2读出a?不能到达终态，或者反之，所以s1和s2不等价。 s1 t1 a s2 t2 a ? i ? j 则将I(i)分成两半，使得一半含有s1 : I(i1)={s|s?I(i)且s经a弧到达t, 且t与t1属于现行?中的同一子集} 另一半含有s2 : I(i2)=I(i)-I(i1) s1 t1 a s2 t2 a ? i ? j 一般地，对某个a和I(i)，若Ia(i) 落入现行?中 N个不同子集，则应把I(i)划分成N个不相交的组，使得每个组J的Ja都落入的?同一子集。这样构成新的划分。 重复上述过程，直到?所含子集数不再增长。 对于上述最后划分?中的每个子集，我们选取每个子集I中的一个状态代表其他状态，则可得到化简后的DFA M’。 若I含有原来的初态，则其代表为新的初态，若I含有原来的终态，则其代表为新的终态。 0 1 2 3 5 4 6 a a b b b a b a a b a b a b I(1)={0, 1, 2} I(2)={3, 4, 5, 6} Ia(1) ={1, 3} I(11) ={0, 2} I(12) ={1} I(2)={3, 4, 5, 6} I(11) ={0, 2} Ia(11) ={1} Ib(11) ={2, 5} I(111) ={0} I(112) ={2} I(12) ={1} I(2)={3, 4, 5, 6} Ia(2) ={3, 6} Ib(2) ={4, 5} 0 1 2 3 5 4 6 a a b b b a b a a b a b a b 0 1 2 3 a a b b b a a b FA 正规集 正规式 DFA NFA 正规文法 3.3.1 3.3.2 3.3.3 3.3.4 3.3.5 DFA 3.3.6 3.4 词法分析器的自动产生--LEX 词法分析程序自动产生器 词法分析程序L LEX源程序 词法分析程序L 单词符号 输入串 状态转换矩阵 控制执行程序 AUXILIARY DEFINITION letter?A|B|...|Z digit ?0|1|...|9 RECOGNITION RULES 1 DIM { RETURN (1,-) } 2 IF { RETURN (2,-) } 3 DO { RETURN (3,-) } 4 STOP { RETURN (4,-) } 5 END { RETURN (5,-) } 6 letter(letter|digit) * { RETURN (6, TOKEN) } 7 digit(digit)* { RETURN (7, DTB) } 8 = { RETURN (8, -) } 9 + { RETURN (9,-) } 10 * { RETURN (10,-) } 11 ** { RETURN (11,-) } 12 , { RETURN (12,-) } 13 ( { RETURN (13,-) } 14 ) { RETURN (14,-) } 正规式 LEX的工作过程： 首先，对每条识别规则Pi构造一个相应的非确定有限自动机Mi； 然后，引进一个新初态X，通过?弧，将这些自动机连接成一个新的NFA； 最后，把M确定化、最小化，生成该DFA的状态转换表和控制执行程序 X ? P2 ? ? ? M1 Mm M2 P1 Pm ? ? 作业 P64-7，8，12，14 例: 对下图NFA M构造其DFA. a a b b b X Y 解: 用子集法构造转换矩阵 不可识别ba ! {1, 2} {0} b a,b a b 0 2 1 DFA M’ a,b a b 0 1 化简后的DFA M’ ba ！！！ 3.3.4 正规文法与有限自动机的等价性 定理： 1.对每一个右线性正规文法G或左线性正规文法G，都存在一个有限自动机