编译原理-第三版-第三章-习题与答案（修改后）.doc

<p><span id="_baidu_bookmark_start_0" style="display: none; line-height: 0px;">‍</span>第3章 习题
&nbsp;
3-1 &nbsp;试构造一右线性文法,使得它与如下得文法等价
S→AB &nbsp; &nbsp; A→UT &nbsp; &nbsp; U→aU|a &nbsp; &nbsp;D→bT|b &nbsp; B→cB|c
并根据所得得右线性文法,构造出相应得状态转换图。
3-2 &nbsp;对于如题图3-2所示得状态转换图

(1) 写出相应得右线性文法;
(2) 指出它接受得最短输入串;
(3) 任意列出它接受得另外4个输入串;
(4) 任意列出它拒绝接受得4个输入串。
3-3 &nbsp;对于如下得状态转换矩阵:

(1) 分别画出相应得状态转换图;
(2) 写出相应得3型文法;
(3) 用自然语言描述它们所识别得输入串得特征。
3-4 &nbsp;将如下得NFA确定化与最小化:

3-5 &nbsp;将如题图3-5所示得具有ε动作得NFA确定化。

题图3-5 &nbsp;具有ε动作得NFA
&nbsp; &nbsp;3-6 &nbsp;设有文法G[S]:
S→aA &nbsp; &nbsp; A→aA|bB &nbsp; &nbsp; B→bB|cC|c &nbsp; &nbsp; C→cC|c
试用正规式描述它所产生得语言。
&nbsp; &nbsp;3-7 &nbsp;分别构造与如下正规式相应得NFA。
(1) ((0* |1)(1* 0))*
(2) b|a(aa*b)*b
3-8 &nbsp;构造与正规式(a|b)*(aa|bb)(a|b)*相应得DFA。
第3章 习题答案
3-1 &nbsp;解:根据文法知其产生得语言就是:
L[G]={ambnci| m,n,i≧1}
可以构造与原文法等价得右线性文法:
S→aA &nbsp; &nbsp; A→aA|bB &nbsp; &nbsp; B→bB|cC|c &nbsp; &nbsp; C→cC|c
其状态转换图如下:

3-2 &nbsp;解:
(1) 其对应得右线性文法就是G[A]:
A →0D &nbsp; &nbsp; &nbsp; B→0A|1C &nbsp; &nbsp; &nbsp;C→0A|1F|1
D→0B|1C &nbsp; &nbsp; E→0B|1C &nbsp; &nbsp; &nbsp;F→1A|0E|0
(2) 最短输入串为011
(3) 任意接受得四个输入串为:
0110,0011,000011,00110
(4) 任意拒绝接受得输入串为:
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;0111,1011,1100,1001
3-3 &nbsp;解:
(1) 相应得状态转换图为:

(2) 相应得3型文法为:
(ⅰ) S→aA|bS &nbsp; &nbsp; A→aA|bB|b &nbsp; &nbsp; B→aB|bB|a|b
(ⅱ) S→aA|bB|a &nbsp; &nbsp; A→bA|aC|a|b &nbsp; &nbsp; B→aB|bC|b &nbsp; &nbsp; C→aC|bC|a|b
(ⅲ) S→aA|bB|b &nbsp; &nbsp;A→aB|bA|a &nbsp; &nbsp; B→aB|bB|a|b
(ⅳ) S→bS|aA &nbsp; &nbsp; A→aC|bB|a &nbsp; &nbsp; B→aB|bC|b &nbsp; &nbsp; C→aC|bC|a|b
(3) 用自然语言描述得输入串得特征为:
(ⅰ) 以任意个(包括0个)b开头,中间有任意个(大于1)a,跟一个b,还可以有一个由a,b组成得任意字符串。
(ⅱ) &nbsp;以a打头,中间有任意个(包括0个)b,再跟a,最后由一个a,b所组成得任意串结尾;或者以b打头,中间有任意个(包括0个)a,再跟b,最后由一个a,b所组成得任意串结尾。
(ⅲ) 以a打头,后跟任意个(包括0个)b ,再跟a,最后由一个a,b所组成得任意串结尾;或者以b打头,由一个a,b所组成得任意串结尾。
(ⅳ) 以任意个(包括0个)b开头,中间跟aa,最后由一个a,b所组成得任意串结尾;或者以任意个(包括0个)b开头,中间跟ab后,再接任意个(包括0个)a,再接b,最后由一个a,b所组成得任意串结尾。
3-4 &nbsp;解:
(1) 将NFA M确定化后得DFA M′,其状态转换矩阵如答案图3-4-(1)之(a)所示,给各状态重新命名,即令:
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[S]=1, &nbsp; &nbsp;[S,A]=2, &nbsp; &nbsp;[A,B]=3, &nbsp; &nbsp;[B]=4
且由于3及4得组成中均含有M得终态B,故3与4组成了DFA &nbsp;M′得终态集Z′。于就是,所构造之DFA M′得状态转换矩阵与状态转换图如答案图3-4-(1)之(b)及(c)所示。

现将DFA M′最小化:
(ⅰ)初始分划由两个子集组成,即
π0:{1,2}, {3,4}
(ⅱ)为得到下一分划,考察子集{1,2}。因为
{2}b ={3}Ì{3,4}
但 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{1}b =Æ
故1与2可区分,于就是便得到下一分划
π1: {1}, {2}, {3,4}
(ⅲ)又因π1≠π0 ,再考虑{3,4},因为
{3}b ={3}Ì{3,4}
而 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{4}b =Æ
故3与4可区分,从而又得到
π2: {1}, {2}, {3}, {4}
此时子集已全部分裂,故最小化得过程宣告结束,M′即为状态数最小得DFA。
(2) 将NFA M确定化后得DFA M′,其状态转换矩阵如答案图3-4-(2)之(a)所示,给各状态重新命名,即令:
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[S]=1, &nbsp; &nbsp;[A]=2, &nbsp; &nbsp;[B,C]=3
且由于3得组成中含有M得终态C,故3为DFA M′得终态。于就是,所构造之DFA M′得状态转换矩阵与状态转换图如答案图3-4-(2)之(b)及(c)所示。

现将DFA M′最小化:
(ⅰ)初始分划由两个子集组成,即
π0:{1,2}, {3}
(ⅱ)为得到下一分划,考察子集{1,2}。因为
{2}b ={2}Ì{1,2}
但 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{1}b =Æ
故1与2可区分,于就是便得到下一分划
π1: {1}, {2}, {3}
此时子集已全部分裂,故最小化得过程宣告结束,M′即为状态数最小得DFA。
(3) 将NFA M确定化后得DFA M′,其状态转换矩阵如答案图3-4-(3)之(a)所示,给各状态重新命名,即令:
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[S]=1, &nbsp; &nbsp;[A]=2, &nbsp; &nbsp;[S,B]=3
且由于3得组成中含有M得终态B,故3为DFA M′得终态。于就是,所构造之DFA M′得状态转换矩阵与状态转换图如答案图3-4-(3)之(b)及(c)所示。

现将DFA M′最小化:
(ⅰ)初始分划由两个子集组成,即
π0:{1,2}, {3}
(ⅱ)为得到下一分划,考察子集{1,2}。因为
{2}b ={3}
但 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{1}b =Æ
故1与2可区分,于就是便得到下一分划
π1: {1}, {2}, {3}
此时子集已全部分裂,故最小化得过程宣告结束,M′即为状态数最小得DFA。
(4) 将NFA M确定化后得DFA M′,其状态转换矩阵如答案图3-4-(4)之(a)所示,给各状态重新命名,即令:
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[A]=1, &nbsp; &nbsp;[B,C]=2, &nbsp; &nbsp;[B]=3, &nbsp; &nbsp; [C]=4
且由于2与4得组成中含有M得终态C,故2与4组成了DFA M′得终态集Z′。于就是,所构造之DFA M′得状态转换矩阵与状态转换图如答案图3-4-(4)之(b)及(c)所示。
&nbsp; &nbsp; &nbsp;

现将DFA M′最小化:
(ⅰ)初始分划由两个子集组成,即
π0:{1,3}, {2,4}
(ⅱ)为得到下一分划,考察子集{1,3}。因为
{1}a ={2}Ì{2,4}
但 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{3}a ={1}Ì{1,3}
故1与3可区分,于就是便得到下一分划
π1: {1}, {3}, {2,4}
(ⅲ)又因π1≠π0,再考虑{2,4},因为
{2}a ={4}a ={1}, &nbsp; {2}b ={4}b ={4}
所以2与4不可区分,故子集{S,B}已不能再分裂。此时π2 =π1 ,子集分裂得过程宣告结束。
(ⅳ) 现选择状态2作为{2,4}得代表,将状态4从状态转换图中删去,并将原来引至4得矢线都引至2,这样,我们就得到了最小化后得DFA M〞如答案图3-4-(4)之(d)所示。
3-5 &nbsp;解:
(1) 将具有ε动作得NFA M确定化后得DFA M′,其状态转换矩阵如答案图3-5-(1)之(a)所示,给各状态重新命名,即令:
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[S,B,C]=1, &nbsp; &nbsp;[A]=2, &nbsp; &nbsp;[B,C] =3, &nbsp; &nbsp; [C]=4
且由于1,3与4得组成中均含有M得终态C,故1,3与4组成了DFA M′得终态集Z′。于就是,所构造之DFA M′得状态转换矩阵与状态转换图如答案图3-5-(1)之(b)及(c)所示。

(2) 将具有ε动作得NFA M确定化后得DFA M′,其状态转换矩阵如答案图3-5-(2)之(a)所示,给各状态重新命名,即令:
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[S]=1, &nbsp; &nbsp; &nbsp; &nbsp; [Z]=2, &nbsp; &nbsp; &nbsp; &nbsp; [R,U] =3, &nbsp; &nbsp; [S,X]=4,
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[R,U,Y]=5, &nbsp; &nbsp; [S,U,X]=6, &nbsp; &nbsp; [S,Z]=7, &nbsp; &nbsp; &nbsp;[R,U,Y,Z]=8
且由于2,7与8得组成中均含有M得终态Z,故2,7与8组成了DFA M′得终态集Z′。于就是,所构造之DFA M′得状态转换矩阵与状态转换图如答案图3-5-(2)之(b)及(c)所示。

3-6 &nbsp;解:
首先将文法写成方程组:
S=aA &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (1)
A=aA+bB &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;(2)
B=bB+cC+c &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;(3)
C=cC+c &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (4)
将(4)代入(3),得:
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;B=bB+C &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (5)
由论断3、1,方程(4)得解为:
C=c*c
将上式代入(5),得:
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;B=bB+c*c
由论断3、1,得:
B=b*c*c
将上式代入(2),得:
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;A=aA+b*bc*c
由论断3、1,得:
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;A=a*b*bc*c
将上式代入(1),得:
S=a*ab*bc*c
即文法所产生得语言可用正规式a*ab*bc*c表示。
3-7 &nbsp;解:
(1) 构造与正规式((0* |1)(1* 0))*相应得NFA得步骤如答案图3-7-(1)所示:

(2) 构造与正规式 b|a(aa*b)*b 相应得NFA得步骤如答案图3-7-(2)所示:

答案图3-7-(2) &nbsp;正规式 b|a(aa*b)*b 得NFA
3-8 &nbsp;解:
首先,构造与正规式(a|b)*(aa|bb)(a|b)*相应得NFA M,其构造步骤如答案图3-8(a)所示:

其次,将答案图3-8(a)所示得具有ε动作得NFA M确定化后得到DFA M′,其状态转换矩阵如答案图3-8(b)所示,给各状态重新命名,即令:
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[S,3,1]=S, &nbsp; &nbsp;[3,1,5]=A, &nbsp; &nbsp;[3,1,6] =B, &nbsp; &nbsp; [3,1,5,2,4,Z]=C,
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[3,1,6,2,4,Z]=D, &nbsp; &nbsp; &nbsp; [3,1,6,4,Z]=E, &nbsp; &nbsp; &nbsp; [3,1,5,4,Z]=F
且由于C,D,E与F得组成中均含有NFA M得终态Z,故C,D,E与F组成了DFA M′得终态集Z′。于就是,将NFA M确定化后所得DFA M′得状态转换矩阵与状态转换图如答案图3-8(c)及(d)所示。

(e) &nbsp;对DFA M′最小化后所得得DFA M〞得状态转换图
答案图3-8
&nbsp; &nbsp;最后,将所得DFA M′最小化:
(ⅰ)初始分划由两个子集组成,即
π0:{S,A,B}, {C,D,E,F}
(ⅱ)为得到下一分划,考察子集{S,A,B}。因为
{S,B}a ={A}Ì{S,A,B}
但 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{A}a ={C}Ì{C,D,E,F}
故S,B与A可区分,于就是便得到下一分划
π1: {S,B}, {A}, {C,D,E,F}
(ⅲ)因π1 ≠π0 ,考虑{S,B},因为
{S}b ={B}Ì{S,B}
但 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{B}b ={D}Ì{C,D,E,F}
故S与B可区分,于就是便得到下一分划
π2: {S}, {B}, {A}, {C,D,E,F}
(ⅳ) 又因π2 ≠π1 ,再考虑{C,D,E,F},因为
{C}a ={F}a ={C}, &nbsp; {C}b ={F}b ={E}
所以C与F等价;同理可得D与E等价。又因为
{C}a ={C}, &nbsp; {D}a ={F}, &nbsp;
{C}b ={E}, &nbsp; {D}b ={D}
而C与F等价,D与E等价,所以C与D也等价,故C,D,E,F这4个状态等价。此时π3 =π2 ,子集分裂得过程宣告结束。
(ⅴ)现选择状态C作为{C,D,E,F}得代表,将状态D,E,F从状态转换图中删去,并将原来引至D,E,F得矢线都引至C,这样,我们就得到了最小化后得DFA M〞如答案图3-8(e)所示,此DFA M〞即为所求得与正规式(a|b)*(aa|bb)(a|b)*相应得DFA。</p>