编译原理 第3章习题解答.doc

第三章 习题参考解答 3.1 构造自动机A，使得 当从左至右读入二进制数时，它能识别出读入的奇数； 它识别字母表a, b上的符号串，但符号串不能含两个相邻的a，也不含两个相邻的b； 它能接受字母表0, 1上的符号串，这些符号串由任意的1、0和随后的任意的11、00对组成。 它能识别形式如 dd* d*E dd的实数，其中，d0, 1, 2, 3, 4, 5, 6, 7, 8, 9。 3.2 构造下列正规表达式的DFSA： xy*yx*yxyx； 00(01)*11； 01(1001)*(1100)*01； a(ab*ba*)*b。 3.3 消除图3.24所示自动机的空移。图3.24 含空移的自动机 3.4 将图3.25所示NDFSA确定化和最小化。 图3.25 待确定化的NDFSA 3.5 设e、e1、e2是字母表S上的正规表达式，试证明 ee=e； e=e； e=eee； e1 e2 e1= e1e2 e1; e1e2=e1e2=e1e2。 3.6 构造下面文法GZ的自动机，指明该自动机是不是确定的，并写出它相应的语言： GZ: ZA0 AA0Z10 3.7 设NDFSA M=(x, y,a, b,f, x, y), 其中，f(x, a)=x, y, f(x, b)=y, f(y, a)=, f(y, b)=x, y。试对此NDFSA确定化。 3.8 设文法G单词： 单词标识符无符号整数 标识符字母标识符字母标识符数字 无符号整数数字无符号整数数字 字母ab 数字12试写出相应的有限自动机和状态图。 3.9 图3.29所示的是一个NDFSA A，试构造一个正规文法G，使得L(G)= L(A)。图3.29 FSA A 3.10 构造一个DFSA，它接受S=a, b上的符号串，符号串中的每一个b都有a直接跟在右边；然后，再构造该语言的正规文法。参考答案3.1 解 (1) (2) (3) 依题意，当二进制数的末尾为1时，表示此二进制数为奇数。因此自动机接收由0、1构成的一个二进制串，且串的最后一位必为1（特殊情况下，接收数字1）。构造的自动机如下: (4) 由题中自动机所识别的符号串的要求，得到相应的正规文法： SaB|bA|a|b|e AaB|a BbA|b化简后的DFSA由此正规文法得到相应的状态转换图如右图所示。利 用子集法构造确定的有穷自动机如下表所示(已换名)。 将NFSA确定化为DFSA的过程IIaIbS，Z 0B，Z 1A，Z 2B，Z 1A，Z 2A，Z 2B，Z 1DFSA相应的状态图如右图所示。虽然状态0、1、2都是终止状态，但由于它们的输入符号不相同，所以这三个状态不等价。因此，该DFSA已是最小化的DFSA。 (5) 由题中自动机所识别的符号串的要求：“0与1任意出现，随后的11和00也任意出现”，得到相应的正规表达式为 (1|0)*(11|00)*由此正规表达式得到相应的状态转换图(NFSA)如图所示。利用子集法构造确定的有穷自动机如下表所示(已换名)。II0I1S,A,B,C,Z SA,B,C,E,Z AA,B,C,D,Z BA,B,C,E,Z AA,B,C,E,Z AA,B,C,D,Z BA,B,C,D,Z BA,B,C,E,Z AA,B,C,D,Z BDFSA相应的状态图如下左图所示。对左图所示的DFSA进行最小化：因为该DFSA中所有的状态均是终止状态，且输入0均到达A，输入1均到达B，所以状态S、A、B等价。最小化DFSA如右图所示。 DFSA的状态转换图 最小化后的DFSA (6) 依题意，下面的自动机可以接收形如 dd* d*E dd 的串，其中，d0, 1, 2, 3, 4, 5, 6, 7, 8, 93.2 解： 根据题中所给的正规表达式得到相应的状态转换系统左下图所示。依据该状态转换系统构造确定DFSA如表中(已换名)所示。DFSA相应的状态图如右下图所示。 正规表达式的DFSA DFSA的状态转换图将NFSA确定化为DFSA的过程IIxIyS 0A，B，F，Z 1C，D，E 2A，B，F，Z 1B，G，Z 3C，D，E 2D，E 4Z 5B，G，Z 3Z 5B，Z 6D，E 4D，E 4Z 5Z 5B，Z 6B，Z 6对DFSA进行最小化，过程如下：已知K=0，1，2，3，4，5，6。首先将K分成两个子集 K1=0，2，4 (非终态集) K2=1，3，5，6 (终态集)在K1=0，2，4中，因为 0x=1K2 2，4x=4K1所以状态0与状态2、4不等价，故K1可分割为 K11=0 K12=2，4在K12=2，4中，因为有 2，4x =4 2，4y=5K2所以，状态2和状态4等价。 正规表达式xy*|yx*y|xyx的最小化DFSA在K2=1，3，5，6中，状态5无输入，状态3有x、y输入，状态1与状态6均只有y输入，所以可将K2分割为K21=1，6 K22=3 K23=5由于状态1输入y到达状态3，状态6输入y到达状态6，所以状态1与6也不等价。进一步将K21分割为 K211=1 K212=6于是，将原状态集合划分为 0、2，4、1、3、5、6最小化后的状态图如右图所示。 对应于该正规表达式的状态转换图如左下图所示，由造表法确定化、化简后，得到如右图所示的自动机(由于构造自动机的步骤和上一小题完全一样，所以这里只给出最后的结果，中间过程省略)： 对应于该正规表达式的自动机如下图所示：确定化、化简后得到的自动机如下图所示： 根据题中所给的正规表达式得到相应状态转换系统如下左图所示。依据该状态转换系统构造确定DFSA的状态图如下右图所示： 最后化简，得到DFSA如下图所示：3.3 解：去掉弧，和空移环路后的自动机如下图所示：其中状态3是不可达状态，在确定化和化简的过程中应被删除掉（确定化和化简过程略）。3.4 解：依据该NFSA的状态图构造DFSA如下表所示(已换名)。IIxIyq0 0q1 1q2 2q1 1q2，q3 3q2 2q1，q3 4q2，q3 3q3，q4 5q1，q3 4q1，q3 4q2，q3，q4 6q3 7q3，q4 5q3，q4 5q3 7q2，q3 ，q4 6q3，q4 5q1，q3 4q3 7q3，q4 5q3 7DFSA相应的状态图如下图所示。对DFSA进行最小化，过程如下：已知K=0，1，2，3，4，5，6，7。首先将K分成两个子集 K1=0，1，2，3，4，7 (非终态集) K2=5，6 (终态集)在K1=0，1，2，3，4，7中，因为状态1只有x输入，状态2只有y输入，其它状态均有x、y输入，所以将K1分割为 K11=0，3，4，7 K12=1， K13=2由于在K11中， 0x=1K12 3,4,7x=5,6K2因此将K11分割为 K111=0 K111=3，4，7 由于 3,4,7x=5,6K2 3,4,7y=4,7K111因此状态3、4、7是否等价取决于对K2的划分结果。在状态K2=5，6中， 5,6x=5K2 5,6y=4,7K111所以状态5、6等价，从而状态3、4、7等价。于是，将原状态集合划分为 0、3，4，7、1、2、5，6最小化后的状态图如下图所示。3.5 证明略。3.6 解：该文法是左线性文法，因而需要增加一个开始状态来构造其对应的状态图。得到如下图所示的状态转换图。所以，该文法的自动机为 M=(S，A，Z，0，1，P，S，Z) 其中，P为 d(S，0)=A d(A，0)=A，Z d(Z，1)=A由于在状态A输入0既可以到达状态A，又可以到达状态Z，因此该自动机是不确定的。其相应的语言为L(GZ)=a|a是由0和1组成的以0开头、以0结尾的符号串，并且该符号串不含有两个连续的1其正规表达式为 0(0|01)*03.7 解：该NFSA对应的状态转换图如下图所示。 依据该NDFSA的状态图构造DFSA如下右表所示(已换名)。IIaIbx 0x，y 1y 2x，y 1x，y 1x，y 1y 2x，y 1所以确定的有穷自动机为 M=(0，1，2，a，b，f，0，1，2) 其中，f为 f(0，a)=1 f(0，b)=2 f(1，a)=1 f(1，b)=1 f(2，b)=13.8 解：因为该文法存在直接左递归，所以用扩展的BNF表示法消除左递归。单词标识符无符号整数标识符字母字母数字无符号整数数字数字字母ab数字12此文法描述的语言为标识符和无符号整数。用符号T,I,N,L和D分别表示单词、标识符、无符号整数、字母和数字，按照文法定义的标识符和无符号整数的构成规则，得到以下的正规文法TaI|bI|1N|2N|a|b|1|2IaI|bI|1I|2I|a|b|1|2N1N|2N|1|2然后根据本章中介绍的方法得到相应自动机的状态转换图。（略）3.9 解：根据该NFSA的状态转换图可知：该自动机接受的句子为(a|b)*(aa|bb)(a|b)*为此，构造正规文法如下。 GS：SaS|bS|aA|bB AaC|a BbC|b CaC|bC|a|b经检验，文法GS所识别的句子正是该自动机接受的句子，即L(G)=L(A)。3.10 解： 正规文法为SaS|bA|a|AaS |a