词法分析习题参考答案词法分析习题参考答案1、构造下列正则式相应的、构造下列正则式相应的 DFA （1）1(0|1)* 101 解：解：NFANFA 变换变换 DFA 的子集法过程的子集法过程重新命名：重新命名：DFA 状态转换图状态转换图01-01 111 2 1 21 31 2 1 31 1 2 4 +1 2 41 31 201- 01 112 232 314 + 43200， 123101 4110023111 401100 1（3）a(a | b)*| ab*a)*b NFA 构造过程：构造过程：或或 (a | b)*| ab*a)*baba(a | b)*| ab*a(a | b)*ab*aba(a | b)*| ab*abaNFA 到到 DFA 构造过程：构造过程：Sab0 -0 1 1,2 1 1,2 2 1,2,3 3 1,2,42 1,2,3 2 1,2,3 4 1,2,3,43 +1,2,4 2 1,2,3 3 1,2,44 +1,2,3,4 2 1,2,3 4 1,2,3,4DFA：132a | bbaa04bab1b03a 、a24ababba2已知已知 NFA,构造相应的构造相应的 DFANFA 矩阵矩阵NFA =DFADFA 更名更名01-XZXYX, Y +ZX, ZY01- XZX ZX ZY X ZX ZX Y YX Y +X YX Y ZX +X Y ZX Y ZX Y01- 010 123 224 34 +450 +554DFA 之状态转换图：之状态转换图：02100 50140103111=3将图将图 4.20 确定化：确定化：解：解：NFA 变换变换 DFA 的子集法过程的子集法过程01- SV QU Q V QV ZU Q U QVU Q Z VZ +V ZZZ +U Q ZV ZU Q Z +ZZZ重新命名：重新命名：01- 012 142 235 36 +466 +545 +666DFA 状态转换图状态转换图001Q1b1SZUV 010， 10， 115300000421 01 b10， 10， 161 14把图把图 4.21 的（的（a）分别确定化和最小化）分别确定化和最小化确定化：确定化：重新命名：重新命名：最小化：最小化： 步骤步骤 1. 依据一致性条件，终态和非终态一定不等价。依据一致性条件，终态和非终态一定不等价。将状态集将状态集 0，1，2划分成如下两个子集：划分成如下两个子集：0，1，2=0，1 2 步骤步骤 2：依据蔓延性条件，分解子集：依据蔓延性条件，分解子集0，1： f(0,a)=1，f(1,a)=1 : 关于关于 a 不可分不可分 f(0,b)=2，f(1,b)=2 : 关于关于 b 不可分不可分 结论：子集结论：子集0，1是不可分的，即是不可分的，即 0 和和 1 是等价的。是等价的。 最小化最小化 DFA：ab+ 0011+01011 10ab+ 012+112 20a,b103aa,b103aaa,b213 aa03b5构造一个构造一个 DFA，它接收，它接收=0，1上所有满足下列条件的字上所有满足下列条件的字 符符 串：每个串：每个 1 都有都有 0 直接跟在右边。然后再构造该语言的正则文法。直接跟在右边。然后再构造该语言的正则文法。DFA:正则文法正则文法:S 0S | 1A | A 0S7. 构造构造 DFANFA :A 10 S0XBaQASab ba,baDb bb bb bb bab bNFA=DFA:DFA:8. 给出下述文法所对应的正则式给出下述文法所对应的正则式S 0A | 1BA 1S | 1B 0S | 0解：用解：用 A 和和 B 定义的右部串，替换定义的右部串，替换 S 定义的右部串中的定义的右部串中的 A 和和 B，得：，得：S 01S | 01 | 10S | 10合并同类项和提取公因子得：合并同类项和提取公因子得：ab- SA Q AABX QQDX + BXQD +DXABDABBQDb bBXSaaAQaBXbaaababbDBbbS (01 | 10)S | (01 | 10)在利用规则在利用规则 2（A xA | y =A x*y）得：）得：S (01 | 10)*(01 | 10)即所求的正则式为：即所求的正则式为：(01 | 10)*(01 | 10)