编译原理 第3章习题解答

1、编译原理 第3章习题解答 第三章 习题参考解答 3.1 构造自动机a，使得 当从左至右读入二进制数时，它能识别出读入的奇数； 它识别字母表a, b上的符号串，但符号串不能含两个相邻的a，也不含两个相邻的b； 它能接受字母表0, 1上的符号串，这些符号串由任意的1、0和随后的任意的11、00对组成。 它能识别形式如 * ?dd? de ?dd 的实数，其中，d?0, 1, 2, 3, 4, 5, 6, 7, 8, 9。 3.2 构造下列正规表达式的dfsa： * xy?yxy?xyx； * 00?(01)?11； * 01(10?01)(11?00)01； * a(ab?ba)b。 3.3 消除

2、图3.24所示自动机的空移。 q2abq4?q3b?q5q6?a,bbq0aaq1 图3.24 含空移的自动机 3.4 将图3.25所示ndfsa确定化和最小化。 xq0yyq2q1xyxq3x,yxq4 图3.25 待确定化的ndfsa 3.5 设e、e1、e2是字母表?上的正规表达式，试证明 e?e=e； e=e； e=?ee； e1 e2 e1= e1e2 e1; e1?e2=e1e2=e1?e2。 3.6 构造下面文法gz的自动机，指明该自动机是不是确定的，并写出它相应的语言： gz: za0 aa0?z1?0 3.7 设ndfsa m=(x, y,a, b,f, x, y), 其中，

3、f(x, a)=x, y, f(x, b)=y, f(y, a)=?, f(y, b)=x, y。试对此ndfsa确定化。 3.8 设文法g单词： 单词标识符?无符号整数 标识符字母?标识符字母?标识符数字 无符号整数数字?无符号整数数字 字母a?b 数字1?2 试写出相应的有限自动机和状态图。 3.9 图3.29所示的是一个ndfsa a，试构造一个正规文法g，使得l(g)= l(a)。 asbba,bdaaa,bca,bb 图3.29 fsa a 3.10 构造一个dfsa，它接受?=a, b上的符号串，符号串中的每一个b都有a直接跟在右边；然后，再构造该语言的正规文法。 参考答案 3.1

4、 解 (1) (2) (3) 依题意，当二进制数的末尾为1时，表示此二进制数为奇数。因此自动机接收 由0、1构成的一个二进制串，且串的最后一位必为1（特殊情况下，接收数字1）。构造的自动机如下: 0,1s1z (4) 由题中自动机所识别的符号串的要求，得到相应的正规文法： sab|ba|a|b|? a aab|a a, b, ? bba|b zs由此正规文法得到相应的状态转换图如右图所示。利 b用子集法构造确定的有穷自动机如下表所示(已换名)。 将nfsa确定化为dfsa的过程 i s，z 0 b，z 1 a，z 2 ia b，z 1 baabba ib a0baa，z 2 a，z 2 1b2

5、b，z 1 化简后的dfsa dfsa相应的状态图如右图所示。虽然状态0、1、2都是终止状态，但由于它们的输入符号不相同，所以这三个状态不等价。因此，该dfsa已是最小化的dfsa。 (5) 由题中自动机所识别的符号串的要求：“0与1任意出现，随后的11和00也任意出现”，得到相应的正规表达式为 (1|0)*(11|00)* 由此正规表达式得到相应的状态转换图(nfsa)如图所示。 d1s?a0?b?0e1c01?z 利用子集法构造确定的有穷自动机如下表所示(已换名)。 i s,a,b,c,z s a,b,c,e,z a a,b,c,d,z b i0 a,b,c,e,z a a,b,c,e,z

6、 a a,b,c,e,z a i1 a,b,c,d,z b a,b,c,d,z b a,b,c,d,z b dfsa相应的状态图如下左图所示。对左图所示的dfsa进行最小化：因为该dfsa中所有的状态均是终止状态，且输入0均到达a，输入1均到达b，所以状态s、a、b等价。最小化dfsa如右图所示。 0s10ba1100, 1s dfsa的状态转换图 最小化后的dfsa (6) 依题意，下面的自动机可以接收形如 ?dd*? d*e ?dd 的串，其中，d?0, 1, 2, 3, 4, 5, 6, 7, 8, 9 s ?1dd2.d3e4?5d6dz 3.2 解： 根据题中所给的正规表达式得到相应

7、的状态转换系统左下图所示。 依据该状态转换系统构造确定dfsa如表中(已换名)所示。dfsa相应的状态图如右下图所示。 axsxfyc?xd?yyby?zxg0y2x1yxxyy3yxy6e4 5 正规表达式的dfsa dfsa的状态转换图 将nfsa确定化为dfsa的过程 i s 0 ix a，b，f，z 1 iy c，d，e b，g，z 4 5 4 z b，z z 2 3 5 6 5 a，b，f，z 1 c，d，e 2 b，g，z 3 d，e z d，e d，e 4 z b，z 5 6 b，z 6 对dfsa进行最小化，过程如下： 已知k=0，1，2，3，4，5，6。首先将k分成两个子集

8、k1=0，2，4 (非终态集) k2=1，3，5，6 (终态集) 在k1=0，2，4中，因为 0x=1?k2 2，4x=4?k1 所以状态0与状态2、4不等价，故k1可分割为 k11=0 k12=2，4 在k12=2，4中，因为有 2，4x =4 2，4y=5?k2 所以，状态2和状态4等价。 在k2=1，3，5，6中，状态5无输入，状态3有x、y输入，状态1与状态6均只有y输入，所以可将k2分割为 yyyk21=1，6 k22=3 k23=5 136x由于状态1输入y到达状态3，状态6输入y到 达状态6，所以状态1与6也不等价。进一步将0xxk21分割为 yy k211=1 k212=6 25 于是，将原状态集合划分为 正规表达式xy*|yx*y|xyx 0、2，4、1、3、5、6 最小化后的状态图如右图所示。 的最小化dfsa 对应于该正规表达式的状态转换图如左下图所示，由造表法确定化、化简后，得到如右图所示的自动机(由于构造自动机的步骤和上一小题完全一样，所以这里只给出最后的结果，中间过程省略)： 10s0?02341?z1s02131141 101 对应于该正规表达式的自动机如下图所示： 7019?50114016?2030s0111 确定化、化简后得到的自动机如下图所示： 00s1112 13000100 051 根据题中所给的正规表达式得到