第3章习题3-1 试构造一右线性文法，使得它与如下的文法等价S→AB A→UT U→aU|a D→bT|b B→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 具有ε动作的NFA3-6 设有文法G[S]：S→aA A→aA|bB B→bB|cC|c C→cC|c 试用正规式描述它所产生的语言。

3-7 分别构造与如下正规式相应的NFA。

(1) ((0* |1)(1* 0))*(2) b|a(aa*b)*b3-8 构造与正规式(a|b)*(aa|bb)(a|b)*相应的DFA。

第3章习题答案3-1 解：根据文法知其产生的语言是:L[G]={a m b n c i| m,n,i≧1}可以构造与原文法等价的右线性文法:S→aA A→aA|bB B→bB|cC|c C→cC|c 其状态转换图如下:3-2 解:(1) 其对应的右线性文法是G[A]:A →0D B→0A|1C C→0A|1F|1D→0B|1C E→0B|1C F→1A|0E|0(2) 最短输入串为011(3) 任意接受的四个输入串为：0110,0011,000011,00110(4) 任意拒绝接受的输入串为：0111，1011，1100，10013-3 解:(1) 相应的状态转换图为：(2) 相应的3型文法为：(ⅰ) S→aA|bS A→aA|bB|b B→aB|bB|a|b(ⅱ) S→aA|bB|a A→bA|aC|a|b B→aB|bC|b C→aC|bC|a|b(ⅲ) S→aA|bB|b A→aB|bA|a B→aB|bB|a|b(ⅳ) S→bS|aA A→aC|bB|a B→aB|bC|b C→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) 将NFA M确定化后得DFA M′，其状态转换矩阵如答案图3-4-(1)之(a)所示，给各状态重新命名，即令：[S]=1, [S,A]=2, [A,B]=3, [B]=4且由于3及4的组成中均含有M的终态B，故3和4组成了DFA M′的终态集Z′。

于是，所构造之DFA M′的状态转换矩阵和状态转换图如答案图3-4-(1)之(b)及(c)所示。

现将DFA M′最小化：(ⅰ)初始分划由两个子集组成，即π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) 将NFA M确定化后得DFA M′，其状态转换矩阵如答案图3-4-(2)之(a)所示，给各状态重新命名，即令：[S]=1, [A]=2, [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}但 {1}b =故1和2可区分，于是便得到下一分划π1: {1}, {2}, {3}此时子集已全部分裂，故最小化的过程宣告结束，M′即为状态数最小的DFA。

(3) 将NFA M确定化后得DFA M′，其状态转换矩阵如答案图3-4-(3)之(a)所示，给各状态重新命名，即令：[S]=1, [A]=2, [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}但 {1}b =故1和2可区分，于是便得到下一分划π1: {1}, {2}, {3}此时子集已全部分裂，故最小化的过程宣告结束，M′即为状态数最小的DFA。

(4) 将NFA M确定化后得DFA M′，其状态转换矩阵如答案图3-4-(4)之(a)所示，给各状态重新命名，即令：[A]=1, [B,C]=2, [B]=3, [C]=4且由于2和4的组成中含有M的终态C，故2和4组成了DFA M′的终态集Z′。

于是，所构造之DFA M′的状态转换矩阵和状态转换图如答案图3-4-(4)之(b)及(c)所示。

现将DFA M′最小化：(ⅰ)初始分划由两个子集组成，即π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，这样，我们就得到了最小化后的DFA M〞如答案图3-4-(4)之(d)所示。

3-5 解：(1) 将具有ε动作的NFA M确定化后得DFA M′，其状态转换矩阵如答案图3-5-(1)之(a)所示，给各状态重新命名，即令：[S,B,C]=1, [A]=2, [B,C] =3, [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)所示，给各状态重新命名，即令：[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组成了DFA M′的终态集Z′。

于是，所构造之DFA M′的状态转换矩阵和状态转换图如答案图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 的NFA3-8 解：首先，构造与正规式(a|b)*(aa|bb)(a|b)*相应的NFA M，其构造步骤如答案图3-8(a)所示：其次，将答案图3-8(a)所示的具有ε动作的NFA M确定化后得到DFA M′，其状态转换矩阵如答案图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的组成中均含有NFA M的终态Z，故C,D,E和F组成了DFA M′的终态集Z′。

于是，将NFA M确定化后所得DFA M′的状态转换矩阵和状态转换图如答案图3-8(c)及(d)所示。

(e) 对DFA M′最小化后所得的DFA M〞的状态转换图答案图3-8最后，将所得DFA M′最小化：(ⅰ)初始分划由两个子集组成，即π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，这样，我们就得到了最小化后的DFA M〞如答案图3-8(e)所示,此DFA M〞即为所求的与正规式(a|b)*(aa|bb)(a|b)*相应的DFA。