编译原理 第3章习题解答

    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*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是字母表上的正规表达式，试证明

    ① ee=e；② {{e}}={e}；③ {e}=e{e}；④ {e1 e2} e1= e1{e2 e1};

⑤ {e1e2}={{e1}{e2}}={{e1}{e2}}。

    3.6 构造下面文法G[Z]的自动机，指明该自动机是不是确定的，并写出它相应的语言：

        G[Z]:

           Z→A0

           A→A0Z10

    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，它接受={a, b}上的符号串，符号串中的每一个b都有a直接跟在右边；然后，再构造该语言的正规文法。

参

3.1 解 (1) 

(2)                

(3) 依题意，当二进制数的末尾为1时，表示此二进制数为奇数。因此自动机接收由0、1构成的一个二进制串，且串的最后一位必为1（特殊情况下，接收数字1）。构造的自动机如下:

   (4) 由题中自动机所识别的符号串的要求，得到相应的正规文法：

        S→aB|bA|a|b|

        A→aB|a

        B→bA|b

化简后的DFSA

由此正规文法得到相应的状态转换图如右图所示。利    用子集法构造确定的有穷自动机如下表所示(已换名)。

          将NFSA确定化为DFSA的过程

    (5) 由题中自动机所识别的符号串的要求：“0与1任意出现，随后的11和00也任意出现”，得到相应的正规表达式为     (1|0)*(11|00)*

由此正规表达式得到相应的状态转换图(NFSA)如图所示。

利用子集法构造确定的有穷自动机如下表所示(已换名)。

                        DFSA的状态转换图                     最小化后的DFSA

   (6) 依题意，下面的自动机可以接收形如 dd* d*E dd 的串，其中，d{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

3.2 解：① 根据题中所给的正规表达式得到相应的状态转换系统左下图所示。

依据该状态转换系统构造确定DFSA如表中(已换名)所示。DFSA相应的状态图如右下图所示。

                 正规表达式的DFSA                        DFSA的状态转换图

将NFSA确定化为DFSA的过程

已知K={0，1，2，3，4，5，6}。首先将K分成两个子集

      K1={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 ={4}     {2，4}y={5}K2

所以，状态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如下表所示(已换名)。

对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中，

                    {0}x=1K12          {3,4,7}x={5,6}K2

因此将K11分割为

                    K111={0}             K111={3，4，7} 

由于

                       {3,4,7}x={5,6}K2    {3,4,7}y={4,7}K111

因此状态3、4、7是否等价取决于对K2的划分结果。

在状态K2={5，6}中，

        {5,6}x=5K2          {5,6}y={4,7}K111

所以状态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为

       (S，0)={A}

       (A，0)={A，Z}

       (Z，1)={A}

由于在状态A输入0既可以到达状态A，又可以到达状态Z，因此该自动机是不确定的。其相应的语言为

L(G[Z])={a|a是由0和1组成的以0开头、以0结尾的符号串，并且该符号串不含有两个连续的1}

其正规表达式为  0(0|01)*0

3.7 解：该NFSA对应的状态转换图如下图所示。

依据该NDFSA的状态图构造DFSA如下右表所示(已换名)。

        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)=1

3.8 解：因为该文法存在直接左递归，所以用扩展的BNF表示法消除左递归。

〈单词〉→〈标识符〉〈无符号整数〉

〈标识符〉→〈字母〉{〈字母〉〈数字〉}

〈无符号整数〉→〈数字〉{〈数字〉}

〈字母〉→ab

〈数字〉→12

此文法描述的语言为标识符和无符号整数。用符号T,I,N,L和D分别表示〈单词〉、〈标识符〉、〈无符号整数〉、〈字母〉和〈数字〉，按照文法定义的标识符和无符号整数的构成规则，得到以下的正规文法

T→aI|bI|1N|2N|a|b|1|2

I→aI|bI|1I|2I|a|b|1|2

N→1N|2N|1|2

然后根据本章中介绍的方法得到相应自动机的状态转换图。（略）

3.9 解：根据该NFSA的状态转换图可知：该自动机接受的句子为

(a|b)*(aa|bb)(a|b)*

为此，构造正规文法如下。

        G[S]：S→aS|bS|aA|bB

              A→aC|a

              B→bC|b

              C→aC|bC|a|b

经检验，文法G[S]所识别的句子正是该自动机接受的句子，即L(G)=L(A)。

3.10 解：

正规文法为

S→aS|bA|a|ε

A→aS |a