第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 具有ε动作的NFA
3-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) *b
3-8 构造与正规式(a|b)*(aa|bb)(a|b)*相应的DFA 。
第3章 习题答案
3-1 解：根据文法知其产生的语言是:
L[G]={am 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|1 D→0B|1C E→0B|1C F→1A|0E|0
(2) 最短输入串为011
(3) 任意接受的四个输入串为：
0110,0011,000011,00110
(4) 任意拒绝接受的输入串为： 0111，1011，1100，1001
3-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) 由论断3.1，方程(4)的解为:
C=c*c
将上式代入(5)，得： B=bB+c*c 由论断3.1，得：
B=b*c *c
将上式代入(2)，得： A=aA+b*bc *c 由论断3.1，得： A=a*b *bc *c 将上式代入(1)，得：
S=a*ab *bc *c
即文法所产生的语言可用正规式a *ab *bc *c 表示。
3-7 解：
(1) 构造与正规式((0|1)(10)) 相应的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)*相应的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个状态等价。此时π=π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 。
3
第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 具有ε动作的NFA
3-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) *b
3-8 构造与正规式(a|b)*(aa|bb)(a|b)*相应的DFA 。
第3章 习题答案
3-1 解：根据文法知其产生的语言是:
L[G]={am 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|1 D→0B|1C E→0B|1C F→1A|0E|0
(2) 最短输入串为011
(3) 任意接受的四个输入串为：
0110,0011,000011,00110
(4) 任意拒绝接受的输入串为： 0111，1011，1100，1001
3-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) 由论断3.1，方程(4)的解为:
C=c*c
将上式代入(5)，得： B=bB+c*c 由论断3.1，得：
B=b*c *c
将上式代入(2)，得： A=aA+b*bc *c 由论断3.1，得： A=a*b *bc *c 将上式代入(1)，得：
S=a*ab *bc *c
即文法所产生的语言可用正规式a *ab *bc *c 表示。
3-7 解：
(1) 构造与正规式((0|1)(10)) 相应的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)*相应的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个状态等价。此时π=π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 。
3