蒋立源编译原理第三版第三章习题与答案.docx
《蒋立源编译原理第三版第三章习题与答案.docx》由会员分享，可在线阅读，更多相关《蒋立源编译原理第三版第三章习题与答案.docx（10页珍藏版）》请在冰点文库上搜索。
蒋立源编译原理第三版第三章习题与答案
第3章习题
3-1试构造一右线性文法，使得它与如下的文法等价
S→ABA→UTU→aU|aD→bT|bB→cB|c
并根据所得的右线性文法，构造出相应的状态转换图。
3-2对于如题图3-2所示的状态转换图
（1）写出相应的右线性文法；
（2）指出它接受的最短输入串；
（3）任意列出它接受的另外4个输入串；
（4）任意列出它拒绝接受的4个输入串。
3-3对于如下的状态转换矩阵：
（1）分别画出相应的状态转换图；
（2）写出相应的3型文法；
（3）用自然语言描述它们所识别的输入串的特征。
3-4将如下的NFA确定化和最小化：
3-5将如题图3-5所示的具有ε动作的NFA确定化。
题图3-5具有ε动作的NFA
3-6设有文法G[S]：
S→aAA→aA|bBB→bB|cC|cC→cC|c
试用正规式描述它所产生的语言。
3-7分别构造与如下正规式相应的NFA。
（1）（（0*|1）（1*0））*
（2）b|a（aa*b）*b
3-8构造与正规式（a|b）*（aa|bb）（a|b）*相应的DFA。
第3章习题答案
3-1解：
根据文法知其产生的语言是:
L[G]={ambnci|m,n,i≧1}
可以构造与原文法等价的右线性文法:
S→aAA→aA|bBB→bB|cC|cC→cC|c
其状态转换图如下:
3-2解:
（1）其对应的右线性文法是G[A]:
A→0DB→0A|1CC→0A|1F|1
D→0B|1CE→0B|1CF→1A|0E|0
（2）最短输入串为011
（3）任意接受的四个输入串为：
0110,0011,000011,00110
（4）任意拒绝接受的输入串为：
0111，1011，1100，1001
3-3解:
（1）相应的状态转换图为：
（2）相应的3型文法为：
（ⅰ）S→aA|bSA→aA|bB|bB→aB|bB|a|b
（ⅱ）S→aA|bB|aA→bA|aC|a|bB→aB|bC|bC→aC|bC|a|b
（ⅲ）S→aA|bB|bA→aB|bA|aB→aB|bB|a|b
（ⅳ）S→bS|aAA→aC|bB|aB→aB|bC|bC→aC|bC|a|b
（3）用自然语言描述的输入串的特征为：
（ⅰ）以任意个（包括0个）b开头，中间有任意个（大于1）a，跟一个b，还可以有一个由a,b组成的任意字符串。
（ⅱ）以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解：
（1）将NFAM确定化后得DFAM′，其状态转换矩阵如答案图3-4-
（1）之（a）所示，给各状态重新命名，即令：
[S]=1,[S,A]=2,[A,B]=3,[B]=4
且由于3及4的组成中均含有M的终态B，故3和4组成了DFAM′的终态集Z′。
于是，所构造之DFAM′的状态转换矩阵和状态转换图如答案图3-4-
（1）之（b）及（c）所示。
现将DFAM′最小化：
（ⅰ）初始分划由两个子集组成，即
π0:
{1,2},{3,4}
（ⅱ）为得到下一分划，考察子集{1,2}。
因为
{2}b={3}{3,4}
但{1}b=
故1和2可区分，于是便得到下一分划
π1:
{1},{2},{3,4}
（ⅲ）又因π1≠π0，再考虑{3,4}，因为
{3}b={3}{3,4}
而{4}b=
故3和4可区分，从而又得到
π2:
{1},{2},{3},{4}
此时子集已全部分裂，故最小化的过程宣告结束，M′即为状态数最小的DFA。
（2）将NFAM确定化后得DFAM′，其状态转换矩阵如答案图3-4-
（2）之（a）所示，给各状态重新命名，即令：
[S]=1,[A]=2,[B,C]=3
且由于3的组成中含有M的终态C，故3为DFAM′的终态。
于是，所构造之DFAM′的状态转换矩阵和状态转换图如答案图3-4-
（2）之（b）及（c）所示。
现将DFAM′最小化：
（ⅰ）初始分划由两个子集组成，即
π0:
{1,2},{3}
（ⅱ）为得到下一分划，考察子集{1,2}。
因为
{2}b={2}{1,2}
但{1}b=
故1和2可区分，于是便得到下一分划
π1:
{1},{2},{3}
此时子集已全部分裂，故最小化的过程宣告结束，M′即为状态数最小的DFA。
（3）将NFAM确定化后得DFAM′，其状态转换矩阵如答案图3-4-（3）之（a）所示，给各状态重新命名，即令：
[S]=1,[A]=2,[S,B]=3
且由于3的组成中含有M的终态B，故3为DFAM′的终态。
于是，所构造之DFAM′的状态转换矩阵和状态转换图如答案图3-4-（3）之（b）及（c）所示。
现将DFAM′最小化：
（ⅰ）初始分划由两个子集组成，即
π0:
{1,2},{3}
（ⅱ）为得到下一分划，考察子集{1,2}。
因为
{2}b={3}
但{1}b=
故1和2可区分，于是便得到下一分划
π1:
{1},{2},{3}
此时子集已全部分裂，故最小化的过程宣告结束，M′即为状态数最小的DFA。
（4）将NFAM确定化后得DFAM′，其状态转换矩阵如答案图3-4-（4）之（a）所示，给各状态重新命名，即令：
[A]=1,[B,C]=2,[B]=3,[C]=4
且由于2和4的组成中含有M的终态C，故2和4组成了DFAM′的终态集Z′。
于是，所构造之DFAM′的状态转换矩阵和状态转换图如答案图3-4-（4）之（b）及（c）所示。
现将DFAM′最小化：
（ⅰ）初始分划由两个子集组成，即
π0:
{1,3},{2,4}
（ⅱ）为得到下一分划，考察子集{1,3}。
因为
{1}a={2}{2,4}
但{3}a={1}{1,3}
故1和3可区分，于是便得到下一分划
π1:
{1},{3},{2,4}
（ⅲ）又因π1≠π0，再考虑{2,4}，因为
{2}a={4}a={1},{2}b={4}b={4}
所以2和4不可区分，故子集{S,B}已不能再分裂。
此时π2=π1，子集分裂的过程宣告结束。
（ⅳ）现选择状态2作为{2,4}的代表，将状态4从状态转换图中删去，并将原来引至4的矢线都引至2，这样，我们就得到了最小化后的DFAM〞如答案图3-4-（4）之（d）所示。
3-5解：
（1）将具有ε动作的NFAM确定化后得DFAM′，其状态转换矩阵如答案图3-5-
（1）之（a）所示，给各状态重新命名，即令：
[S,B,C]=1,[A]=2,[B,C]=3,[C]=4
且由于1,3和4的组成中均含有M的终态C，故1,3和4组成了DFAM′的终态集Z′。
于是，所构造之DFAM′的状态转换矩阵和状态转换图如答案图3-5-
（1）之（b）及（c）所示。
（2）将具有ε动作的NFAM确定化后得DFAM′，其状态转换矩阵如答案图3-5-
（2）之（a）所示，给各状态重新命名，即令：
[S]=1,[Z]=2,[R,U]=3,[S,X]=4,
[R,U,Y]=5,[S,U,X]=6,[S,Z]=7,[R,U,Y,Z]=8
且由于2,7和8的组成中均含有M的终态Z，故2,7和8组成了DFAM′的终态集Z′。
于是，所构造之DFAM′的状态转换矩阵和状态转换图如答案图3-5-
（2）之（b）及（c）所示。
3-6解：
首先将文法写成方程组：
S=aA
（1）
A=aA+bB
（2）
B=bB+cC+c（3）
C=cC+c（4）
将（4）代入（3），得：
B=bB+C（5）
由论断，方程（4）的解为:
C=c*c
将上式代入（5），得：
B=bB+c*c
由论断，得：
B=b*c*c
将上式代入
（2），得：
A=aA+b*bc*c
由论断，得：
A=a*b*bc*c
将上式代入
（1），得：
S=a*ab*bc*c
即文法所产生的语言可用正规式a*ab*bc*c表示。
3-7解：
（1）构造与正规式（（0*|1）（1*0））*相应的NFA的步骤如答案图3-7-
（1）所示：
（2）构造与正规式b|a（aa*b）*b相应的NFA的步骤如答案图3-7-
（2）所示：
答案图3-7-
（2）正规式b|a（aa*b）*b的NFA
3-8解：
首先，构造与正规式（a|b）*（aa|bb）（a|b）*相应的NFAM，其构造步骤如答案图3-8（a）所示：
其次，将答案图3-8（a）所示的具有ε动作的NFAM确定化后得到DFAM′，其状态转换矩阵如答案图3-8（b）所示，给各状态重新命名，即令：
[S,3,1]=S,[3,1,5]=A,[3,1,6]=B,[3,1,5,2,4,Z]=C,
[3,1,6,2,4,Z]=D,[3,1,6,4,Z]=E,[3,1,5,4,Z]=F
且由于C,D,E和F的组成中均含有NFAM的终态Z，故C,D,E和F组成了DFAM′的终态集Z′。
于是，将NFAM确定化后所得DFAM′的状态转换矩阵和状态转换图如答案图3-8（c）及（d）所示。
（e）对DFAM′最小化后所得的DFAM〞的状态转换图
答案图3-8
最后，将所得DFAM′最小化：
（ⅰ）初始分划由两个子集组成，即
π0:
{S,A,B},{C,D,E,F}
（ⅱ）为得到下一分划，考察子集{S,A,B}。
因为
{S,B}a={A}{S,A,B}
但{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}
但{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},{C}b={F}b={E}
所以C和F等价；同理可得D和E等价。
又因为
{C}a={C},{D}a={F},
{C}b={E},{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，这样，我们就得到了最小化后的DFAM〞如答案图3-8（e）所示,此DFAM〞即为所求的与正规式（a|b）*（aa|bb）（a|b）*相应的DFA。
升级会员 