编译原理第4章答案

1、编译原理第 4 章答案编译原理习题解答第 1/1 页第 4 章词法分析1。构造对应于以下标准公式的 DFA:(1) 1 (0 | 1)* 101(2)1(1010 * | 1(010)* 1)* 0(3)a(a | b)* | ab * a)* b(4) b(ab)| bb)ab 溶液：(1)1(0 | 1)对应于101的NFA是256 1990 11 1下表通过子集方法将 NFA 转换为 DFA:I A D E B1D B C E B C E F G H I J K L M N I 0 二毛 闭包(MoveTo(l,0)C10E H J L J M N D B F D I K I D B F

2、 O4B1 L 1 0 I 1H 0K 0J 0 0a 1 B 0MC1 1101 n(3)a(a | B)* | ab * a)* B(略) NFA=(x，y, z，0，1)是已知的。m, x，z)其中:m (x, 0) = z， m (y， 0) = x， y， m (z， 0) = x， z， m (x， 1) = x ， m (y， 1) = ,m (z, 1) = y，构造相应的DFA解决方案:根据NFA图，下 列1x 0 z 0 1 00y编译原理问题解决第3页/3下表通过子集方法将 NFA 转换为 DFA:IA C B A C B B I1 =-闭包Moveto (I ,1) c

3、 c d ed e 5£ 4 d £ 6 d下表通过子集方法将 NFA转换为DFA:id =-闭包(移动到(I, d)B E E7E le =£ C C E -闭包1(移动到(I,E)ls =-闭包(移动到(I, s)F6l .=-闭包(移动到(I ,s) )D D A B C D E F D B D S ？aA|bQ A？aA|bB|b B？bD|aQ Q？aQ | bD | b D？bB|aA E?男 |女？ Bd | AE | bdgd7。为文法g构造相应的最小DFA:解决方案:由于没有来自S的输入字符串能够到达状态E和F,状 态 E 和 F 是多余的，将不

4、被考虑。这样， NFA:AA S A B A B Z B Q A B B B B B B D 编译原理练习解答第 7/7页下表通过子集方法将 NFA 转换为 DFA:I 1S2A3Q4B ， Z 5 D ， Z 6 D 7 B 。从上表可以看出 :(1)因为 4， 5 是 DFA 的最终状态， 所以其他的是非最终状态。 状态 集可以分为两个子集 :P1 = 1， 2， 3， 6， 7， P2 = 4， 5在P1，因为2, 3是输入B后的最终状态，1, 6, 7是输入B后 的非最终状态，所以 P1 可以分为P1=1 = 1 , 6, 7, P12=2, 3(3)在P11，1和6中同样，1和7也不

5、等同因此P11可分为：P111=1, p112 = 6, 7(4)查 p112 = 6，7 。因为输入 a 是 2，3，所以 6，7 的等价性由 2， 3 的等价性决定(5) 检查 P12 = 2 ，3 。由于输入 B 是 4，5， 2， 3 是否相等取决于 4， 5 是否相等(6) 检查 p2 = 4 ，5 ，显然 4，5 是否相等取决于 2，3 和 6，7 是否 同时相等因为存在 (4)，也就是说， 6 和 7 是否相等取决于 2 和 3 是否 相等， 4 和 5 是否相等取决于 2 和 3 是否相等。因为存在 (5)，也就是 说，2 和 3 是否相等取决于 4 和 5 是否相等，所以存在

6、 4 和 5 个相等、 2 和 3 个相等以及 6 和 7 个相等(7) 删除上表中的第 3、5 和 7 行，并将剩余行中的第 3、 5 和 7 行 更改为相应的等效状态 2、4 和 6。下表可用 :1 1S2A4B ， Z 6D 可以通过这种方式最小化的 DFA 如下 :1 B2A2A2A2Aa2 A 6 B B 4 la 2A4B, Z6D6Dlb la =-闭 &包 (移动到 (1 ， a) 2A 2A 3Q 给出对应于下列语法的标准公式 :S？1B？ 1S|1 B？0s | 0s = 01 | 01s = 10 | 10s具有 :s = 01s | 10s | 01 | 10

7、=(01 | 10)s |(01 | 10)=(01|10)(01|10)即 (01 |10)(01 | 10)是所需的常规公式溶液:将后两个生产配方代入第一个生产配方为9。最小化图4.18的DFA，它所识别的语言由正常公式描述1a c 3 d c 6 5 b1a b 7 b解决方案：2 a 4图4.18（1）因为 6，7 是 DFA 的最终状态， 而其他是非最终状态， 所以状态 集可以被分成两个子集 ：P1 = 1，2，3，4，5，p2 = （2）因为 F（6， b）=F（7，b）=6 和 6，7 没有其他输入，所以 6，7 是等 价的（3）因为 f （3，c） = f （4，c） = 3，

8、f （3，d） = f （4，d） = 5，f （3，b） = 6， f （4，b） = 7，和6，7是等价的，所以 3，4是等价的（1 ）因为 f （1，b） =f （2，b） = 2，f （1，a） = 3，f （2，a） = 4，和3，4是等价的，所以 1，2 是等价的 （2）状态 5 不等于 1、2、3、4，因为没有输入字符 B。（3）综上所述，上图中的 DFA 状态可分为 ：p = 1 ，2 、3 ，4 、5 、 6，7DFA 以标准形式表示为 ：B1 a c 3d a b 65 bb * a（c | da）* bb *10。构造以下语法的自动机 ：？A0 A ？ A0|S 1 |0这个自动机确定吗？如果你不确定，一定要确定。自动机的相应 语言是什么？由于这种语法的生成式？ A0，A ？A0|S1 没有字符集 VT 的输入， 所以它不是一个确定的自动机。 为了确定其他公式， 必须使用替换法 来获得其相应的正规公式。放s。A0被代入得到的公式a。S1有:A=A0|A01|0二A(0|01)|0=0(0|01)替换 s ？ AO 有语法的正规形式:0(0|01)0，所以，重写语法确