资源描述：
《编译原理 第3章习题解答.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第三章习题参考解答3.1构造自动机A，使得①②③当从左至右读入二进制数时，它能识别出读入的奇数；④它识别字母表{a,b}上的符号串，但符号串不能含两个相邻的a，也不含两个相邻的b；⑤它能接受字母表{0,1}上的符号串，这些符号串由任意的1、0和随后的任意的11、00对组成。⑥它能识别形式如±dd*×d*E±dd的实数，其中，dÎ{0,1,2,3,4,5,6,7,8,9}。3.2构造下列正规表达式的DFSA：①xy*½yx*y½xyx；②00½(01)*½11；③01((10½01)*(11½00))*01；④a(ab*½ba*)
2、*b。3.3消除图3.24所示自动机的空移。图3.24含空移的自动机3.4将图3.25所示NDFSA确定化和最小化。图3.25待确定化的NDFSA3.5设e、e1、e2是字母表S上的正规表达式，试证明①e½e=e；②{{e}}={e}；③{e}=e½e{e}；④{e1e2}e1=e1{e2e1};⑤{e1½e2}={{e1}{e2}}={{e1}½{e2}}。3.6构造下面文法G[Z]的自动机，指明该自动机是不是确定的，并写出它相应的语言：G[Z]:Z→A0A→A0½Z1½03.7设NDFSAM=({x,y},{a,b},f,x
3、,{y}),其中，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所示的是一个NDFSAA，试构造一个正规文法G，使得L(G)=L(A)。图3.29FSAA3.10构造一个DFSA，它接受S={a,b}上的符号串，
4、符号串中的每一个b都有a直接跟在右边；然后，再构造该语言的正规文法。参考答案3.1解(1)(2)(3)依题意，当二进制数的末尾为1时，表示此二进制数为奇数。因此自动机接收由0、1构成的一个二进制串，且串的最后一位必为1（特殊情况下，接收数字1）。构造的自动机如下:(4)由题中自动机所识别的符号串的要求，得到相应的正规文法：S→aB
5、bA
6、a
7、b
8、eA→aB
9、aB→bA
10、b化简后的DFSA由此正规文法得到相应的状态转换图如右图所示。利用子集法构造确定的有穷自动机如下表所示(已换名)。将NFSA确定化为DFSA的过程IIaIb[S，
11、Z]0[B，Z]1[A，Z]2[B，Z]1[A，Z]2[A，Z]2[B，Z]1DFSA相应的状态图如右图所示。虽然状态0、1、2都是终止状态，但由于它们的输入符号不相同，所以这三个状态不等价。因此，该DFSA已是最小化的DFSA。(5)由题中自动机所识别的符号串的要求：“0与1任意出现，随后的11和00也任意出现”，得到相应的正规表达式为(1
12、0)*(11
13、00)*由此正规表达式得到相应的状态转换图(NFSA)如图所示。利用子集法构造确定的有穷自动机如下表所示(已换名)。II0I1[S,A,B,C,Z]S[A,B,C,E,Z]A
14、[A,B,C,D,Z]B[A,B,C,E,Z]A[A,B,C,E,Z]A[A,B,C,D,Z]B[A,B,C,D,Z]B[A,B,C,E,Z]A[A,B,C,D,Z]BDFSA相应的状态图如下左图所示。对左图所示的DFSA进行最小化：因为该DFSA中所有的状态均是终止状态，且输入0均到达A，输入1均到达B，所以状态S、A、B等价。最小化DFSA如右图所示。DFSA的状态转换图最小化后的DFSA(6)依题意，下面的自动机可以接收形如±dd*×d*E±dd的串，其中，dÎ{0,1,2,3,4,5,6,7,8,9}3.2解：①根据题中
15、所给的正规表达式得到相应的状态转换系统左下图所示。依据该状态转换系统构造确定DFSA如表中(已换名)所示。DFSA相应的状态图如右下图所示。正规表达式的DFSADFSA的状态转换图将NFSA确定化为DFSA的过程IIxIy[S]0[A，B，F，Z]1[C，D，E]2[A，B，F，Z]1[B，G，Z]3[C，D，E]2[D，E]4[Z]5[B，G，Z]3[Z]5[B，Z]6[D，E]4[D，E]4[Z]5[Z]5[B，Z]6[B，Z]6对DFSA进行最小化，过程如下：已知K={0，1，2，3，4，5，6}。首先将K分成两个子集K1
16、={0，2，4}(非终态集)K2={1，3，5，6}(终态集)在K1={0，2，4}中，因为{0}x={1}ÌK2{2，4}x={4}ÌK1所以状态0与状态2、4不等价，故K1可分割为K11={0}K12={2，4}在K12={2，4}中，因为有{2，4}x={
