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

第三章 习题参考解答
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*)*b。
3.3 消除图3.24所示自动机的空移。

图3.24 含空移的自动机
3.4 将图3.25所示NDFSA确定化和最小化。

图3.25 待确定化的NDFSA
3.5 设e、e1、e2是字母表S上的正规表达式，试证明
① e½e=e；② {{e}}={e}；③ {e}=e½e{e}；④ {e1 e2} e1= e1{e2 e1};
⑤ {e1½e2}={{e1}{e2}}={{e1}½{e2}}。
3.6 构造下面文法G[Z]的自动机，指明该自动机是不是确定的，并写出它相应的语言：
G[Z]:
Z→A0
A→A0½Z1½0
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[〈单词〉]：
〈单词〉→〈标识符〉½〈无符号整数〉
〈标识符〉→〈字母〉½〈标识符〉〈字母〉½〈标识符〉〈数字〉
〈无符号整数〉→〈数字〉½〈无符号整数〉〈数字〉
〈字母〉→a½b
〈数字〉→1½2
试写出相应的有限自动机和状态图。
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) 由题中自动机所识别的符号串的要求，得到相应的正规文法：

S→aB|bA|a|b|e
A→aB|a
B→bA|b

化简后的DFSA
由此正规文法得到相应的状态转换图如右图所示。利 用子集法构造确定的有穷自动机如下表所示(已换名)。
将NFSA确定化为DFSA的过程
I
Ia
Ib
[S，Z] 0
[B，Z] 1
[A，Z] 2
[B，Z] 1

[A，Z] 2
[A，Z] 2
[B，Z] 1

DFSA相应的状态图如右图所示。虽然状态0、1、2都是终止状态，但由于它们的输入符号不相同，所以这三个状态不等价。因此，该DFSA已是最小化的DFSA。
(5) 由题中自动机所识别的符号串的要求：“0与1任意出现，随后的11和00也任意出现”，得到相应的正规表达式为 (1|0)*(11|00)*
由此正规表达式得到相应的状态转换图(NFSA)如图所示。

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

I
I0
I1
[S,A,B,C,Z] S
[A,B,C,E,Z] A
[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] B
DFSA相应的状态图如下左图所示。对左图所示的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 解：① 根据题中所给的正规表达式得到相应的状态转换系统左下图所示。
依据该状态转换系统构造确定DFSA如表中(已换名)所示。DFSA相应的状态图如右下图所示。

正规表达式的DFSA DFSA的状态转换图
将NFSA确定化为DFSA的过程
I
Ix
Iy
[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={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如下表所示(已换名)。
I
Ix
Iy
[q0] 0
[q1] 1
[q2] 2
[q1] 1
[q2，q3 ] 3

[q2] 2

[q1，q3] 4
[q2，q3] 3
[q3，q4 ] 5
[q1，q3] 4
[q1，q3] 4
[q2，q3，q4] 6
[q3] 7
[q3，q4] 5
[q3，q4 ] 5
[q3] 7
[q2，q3 ，q4] 6
[q3，q4 ] 5
[q1，q3] 4
[q3] 7
[q3，q4 ] 5
[q3] 7
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=1ÎK12 {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=5ÎK2 {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为
d(S，0)={A}
d(A，0)={A，Z}
d(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如下右表所示(已换名)。
I
Ia
Ib
[x] 0
[x，y] 1
[y] 2
[x，y] 1
[x，y] 1
[x，y] 1
[y] 2

[x，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)=1

3.8 解：因为该文法存在直接左递归，所以用扩展的BNF表示法消除左递归。
〈单词〉→〈标识符〉½〈无符号整数〉
〈标识符〉→〈字母〉{〈字母〉½〈数字〉}
〈无符号整数〉→〈数字〉{〈数字〉}
〈字母〉→a½b
〈数字〉→1½2
此文法描述的语言为标识符和无符号整数。用符号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