第三章答案.doc

第三章习题解答
Aho：《编译原理》书中习题
陈：《程序设计语言编译原理》书中习题

(Aho)3.6 描述下列正规式定义的语言
a) 0(0 | 1)*0
解：定义的语言L={以0开头、以0结尾的0、1串}

b) ((e | 0)1*)*
解：定义的语言L={所有0、1串}

c) (0 | 1)*0(0 | 1)(0 | 1)
解：定义的语言L={第3位为0的二进制串}

d) 0*10*10*10*
解：定义的语言L={包含3个1的0、1串}

e) (00 | 11)*((01 | 10)(00 | 11)*(01 | 10)(00 | 11)*)*
解：定义的语言L={包含偶数个0、偶数个1的0、1串}
首先画出正规式对应的NFA：

将它转换为DFA
e-closure({0}) = { 0, 3, 14} = A
e-closure(d({0, 3, 14}, 0)) = {1, 4, 12} = B e-closure(d({0, 3, 14}, 1)) = {2, 5, 13} = C
e-closure(d({1, 4, 12}, 0)) = A e-closure(d({1, 4, 12}, 1)) = {6, 9} = D
e-closure(d({2, 5, 13}, 0)) = D e-closure(d({2, 5, 13}, 1)) = A
e-closure(d({6, 9}, 0)) = {7, 10} = E e-closure(d({6, 9}, 1)) = {8, 11} = F
e-closure(d({7, 10}, 0)) = D e-closure(d({7, 10}, 1)) = {3, 14} = G
e-closure(d({8, 11}, 0)) = G e-closure(d({8, 11}, 1)) = D
e-closure(d({3, 14}, 0)) = {4, 12} = H e-closure(d({3, 14}, 1)) = {5, 13} = I
e-closure(d({4, 12}, 0)) = G e-closure(d({4, 12}, 1)) = D
e-closure(d({5, 13}, 0)) = D e-closure(d({5, 13}, 1)) = G

对此DFA进行化简：
0
1. {B, C, D ,E, F, H, I}, {A, G}
1
2. {B, C, D, E, F, H, I}——{B, F, H}, {C, D, E, I} {A, G}
3. {C, D, E, I}——{C, E, I}, {D} {B, F, H}, {A, G}

A：偶数个0，偶数个1的0、1串
B：奇数个0，偶数个1的0、1串
C：偶数个0，奇数个1的0、1串
D：奇数个0，奇数个1的0、1串

(Aho)3.7 为下列语言写出正规定义（或正规式、正规文法、有限自动机）
a) 包含五个元音，且按顺序排列的所有字母串
解：con→[b-df-hj-np-tv-z]
string→(con)*a(con | a)*(con)*e(con | e)*(con)*i(con | i)*(con)*o(con | o)* (con)*u(con | u)*

b) 字母按字典升序排列的所有字母串
解：a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*p*q*r*s*t*u*v*w*x*y*z*

c) 以/*开始，*/结束的注释，中间不能包含*/，除非包含在"和"中
解：/*([^*"]* | ".*" | *+[^/])****/
其中，/*和*/间出现内容，是三种不同情况的闭包（随意组合出的任意长度的串）
[^*"]*：除了*和"之外所有的符号任意长度的串
".*"：两个引号括起来的串，其内允许任何符号
*+[^/]：出现*的情况，其后跟一个不是/的符号，这主要是避免*后接[^*"]*，产生*/的情况，至于后面跟随多个不是/的符号，第一个之后的内容可与[^*"]*匹配
但还遗漏了一种情况，即*后不跟随任何符号的情况，即立即接注释结尾的*/的情况，这只需在*/之前加一个**即可，有这种情况，与之匹配；没有——e，也匹配

d) 不包含重复数字的数字串
解：0－9十个数字的情况比较复杂，考虑只有0－2三个数字的情况，对应DFA为

状态含义：
s：e
0：最后一个符号为0的数字串
1：最后一个符号为1的数字串
2：最后一个符号为2的数字串
3：死状态

e) 包含至多一个重复数字的数字串
解： 同样可给出DFA，按d)类似方法设计状态即可
f) 包含偶数个0和奇数个1的0、1串
解：DFA为

状态含义与上题3.6 e)相同。
正规式为AB*，其中
A = 1 | 0(00 | 11)*(10 | 01)
B = 00 | 11 | (01 | 10)(00 | 11)*(01 | 10)
DFAà正规式的转换方法见参考资料“NFA to RegEx Conversion.htm”

h) 不包含子串011的0、1串
解：DFA为

状态0：字符串未包含0
状态1：字符串包含子串0
状态2：字符串包含子串01
状态3：字符串包含子串011

正规式为：1*0* | 1*00*1(00*1)* = 1*(0 | 01)*

i) 不包含子序列011的0、1串
解：DFA为

状态0：字符串未包含0
状态1：字符串包含子序列0
状态2：字符串包含子序列01
状态3：字符串包含子序列011

正规式为：1* | 1*00* | 1*00*10*

(Aho)3.14 用正规式表示UNIX的文件名表达式
解：只需将文件名表达式允许的所有操作符用正规式表示出来即可
‘s’——“s”
\c——\c
*——.*
?——.
[s]——[s]

(Aho)3.16 使用Thompson构造法为下列正规式构造NFA，写出每个NFA处理符号串ababbab过程中的状态转换序列
a) (a | b)*
解：NFA为

ababbab状态转换序列：
0à1à2à4à6à1à3à5à6à1à2à4à6à1à3à5à6à1à3à5à6à1à2à4à6à1à3à5à6à7

b) (a* | b*)*
解：NFA为

ababbab状态转换序列：
0à1à2à4à6à8à10à1à3à5à7à9à10à1à2à4à6à8à10à1à3à5à7à5à7à9à10à1à2à4à6à8à10à1à3à5à7à9à10à11

c) ((e | a)b*)*
解：NFA为

ababbab状态转换序列：
0à1à3à5à6à7à8à9à1à3à5à6à7à8à7à8à9à1à3à5à6à7à8à9à10

d) (a | b)*abb(a | b)*
解：NFA为

ababbab状态转换序列：
0à1à2à4à6à1à3à5à6à7à8à9à10à11à12à14à16à11à13à15à16à17

(Aho)3.17 利用子集构造法将3.16题得到的NFA转换为DFA，同样写出分析符号串ababbab过程中的状态转换。
a) 解：
e-closure({0}) = { 0, 1, 2, 3, 7 } = A
e-closure(d(A, a)) = {1, 2, 3, 4, 6, 7} = B
e-closure(d(A, b)) = {1, 2, 3, 5, 6, 7} = C
e-closure(d(B, a)) = B
e-closure(d(B, b)) = C
e-closure(d(C, a)) = B
e-closure(d(C, b)) = C

ababbab状态转换序列：
AàBàCàBàCàCàBàC

b) 解：
e-closure({0}) = { 0, 1, 2, 3, 4, 5, 8, 9, 10, 11 } = A
e-closure(d(A, a)) = {1, 2, 3, 4, 5, 6, 8, 9, 10, 11 } = B
e-closure(d(A, b)) = {1, 2, 3, 4, 5, 7, 8, 9, 10, 11} = C
e-closure(d(B, a)) = B
e-closure(d(B, b)) = C
e-closure(d(C, a)) = B
e-closure(d(C, b)) = C

ababbab状态转换序列：
AàBàCàBàCàCàBàC

c) 解：
e-closure({0}) = { 0, 1, 2, 3, 4, 6, 7, 9, 10 } = A
e-closure(d(A, a)) = {1, 2, 3, 4, 5, 6, 7, 9, 10 } = B
e-closure(d(A, b)) = {1, 2, 3, 4, 6, 7, 8, 9, 10} = C
e-closure(d(B, a)) = B
e-closure(d(B, b)) = C
e-closure(d(C, a)) = B
e-closure(d(C, b)) = C

ababbab状态转换序列：
AàBàCàBàCàCàBàC

d) 解：
e-closure({0}) = { 0, 1, 2, 3, 7 } = A
e-closure(d(A, a)) = {1, 2, 3, 4, 6, 7, 8 } = B
e-closure(d(A, b)) = {1, 2, 3, 5, 6, 7 } = C
e-closure(d(B, a)) = B
e-closure(d(B, b)) = {1, 2, 3, 5, 6, 7, 9 } = D
e-closure(d(C, a)) = B
e-closure(d(C, b)) = C
e-closure(d(D, a)) = B
e-closure(d(D, b)) = {1, 2, 3, 5, 6, 7, 10, 11, 12, 13, 17 } = E
e-closure(d(E, a)) = {1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, 17 } = F
e-closure(d(E, b)) = {1, 2, 3, 5, 6, 7, 11, 12, 13, 15, 16, 17} = G
e-closure(d(F, a)) = F
e-closure(d(F, b)) = {1, 2, 3, 5, 6, 7, 9, 11, 12, 13, 15, 16, 17 } = H
e-closure(d(G, a)) = F
e-closure(d(G, b)) = G
e-closure(d(H, a)) = F
e-closure(d(H, b)) = {1, 2, 3, 5, 6, 7, 10, 11, 12, 13, 15, 16, 17 } = I
e-closure(d(I, a)) = F
e-closure(d(I, b)) = G

ababbab状态转换序列：
AàBàDàBàDàEàFàH

(Aho)3.18 为3.16的正规式直接构造DFA，比较得到结果与3.17结果的状态数。
a) 解：

followpos
1
{1, 2, 3}
2
{1, 2, 3}
3

firstpos(root) = {1, 2, 3} = A
d(A, a) = followpos(1) = { 1, 2, 3 } = A
d(A, b) = followpos(1) = { 1, 2, 3 } = A

b) 解：

followpos
1
{1, 2, 3}
2
{1, 2, 3}
3

firstpos(root) = {1, 2, 3} = A
d(A, a) = followpos(1) = { 1, 2, 3 } = A
d(A, b) = followpos(1) = { 1, 2, 3 } = A

c) 解：

followpos
1
{1, 2, 3}
2
{1, 2, 3}
3

firstpos(root) = {1, 2, 3} = A
d(A, a) = followpos(1) = { 1, 2, 3 } = A
d(A, b) = followpos(1) = { 1, 2, 3 } = A

d) 解：

followpos
1
{1, 2, 3}
2
{1, 2, 3}
3
{4}
4
{5}
5
{6, 7, 8}
6
{6, 7, 8}
7
{6, 7, 8}
8

firstpos(root) = {1, 2, 3} = A
d(A, a) = followpos(1)∪followpos(3) = { 1, 2, 3, 4 } = B
d(A, b) = followpos(2) = A
d(B, a) = followpos(1)∪followpos(3) = B
d(B, b) = followpos(2)∪followpos(4) = { 1, 2, 3, 5 } = C
d(C, a) = followpos(1)∪followpos(3) = B
d(C, b) = followpos(2)∪followpos(5) = { 1, 2, 3, 6, 7, 8} = D
d(D, a) = followpos(1)∪followpos(3)∪followpos(6) = { 1, 2, 3, 4, 6, 7, 8 } = E
d(D, b) = followpos(2)∪followpos(7) = D
d(E, a) = followpos(1)∪followpos(3)∪followpos(6) = E
d(E, b) = followpos(2)∪followpos(4)∪followpos(7) = { 1, 2, 3, 5, 6, 7, 8 } = F
d(F, a) = followpos(1)∪followpos(3)∪followpos(6) = E
d(A, b) = followpos(2)∪followpos(7) = D

(Aho)3.21 最小化3.18得到的DFA
d) 解：
b
初始划分：{A, B, C}, {D, E, F}
b
{A, B, C}——{A, B}, {C}
{A, B}——{A}, {B}

3.22 正规式的等价可以通过对应的最小化的DFA的结构等价性来证明，利用这种方法，证明下列正规式的等价性
a) (a | b)*
b) (a* | b*)*
c) ((e | a)b*)*
由16、17、18、21结果可知

（陈）7 构造下列正规式对应的DFA
解法：可正规式àNFAàDFA，或者正规式àDFA
a) 1(0 | 1)*101

b) 1(1010* | 1(010)*1)*0

c) 0*10*10*10*

d) (00 | 11)*((01 | 10)(00 | 11)*(01 | 10)(00 | 11)*)*

（陈）8 为下列语言写出正规定义（或正规式、正规文法、有限自动机）
a) 以01结尾的0、1串
解：(0 | 1)*01

b) 能被5整除的十进制整数
解：[1-9][0-9]*(0 | 5) | 0 | 5

c) 包含奇数个1和奇数个0的二进制串
解：(00 | 11)*(01 | 10)((01 | 10)+(00 | 11)*(01 | 10)+)*
解法见Aho3.7f

（陈）10 一个人带一只狼、一只羊和一颗白菜过河，每次人只能将一样东西摆渡到对岸。而在无人的情况下，狼会吃掉羊，羊会吃掉白菜。目标，人将三样东西都摆渡到对岸，羊和白菜都不被吃掉。利用有限自动机得到渡河的方法
解：M——人，W——狼，S——羊，C——白菜，
状态——哪些东西在原岸，如：MWS，表示人、狼、羊在原岸（白菜在目的岸）
动作——人将一样东西摆渡到对岸（原à目的——表示为à，也可能是目的à原——表示为ß）
不满足要求的状态为死状态，如：WS、SC、…
初态：MWSC，终态：e，初态到终态的一条路径——渡河方案。

d(MWSC, àMW) = SC （红色表示死状态）
d(MWSC, àMS) = WC
d(MWSC, àMC) = WS
d(MWSC, àM) = WSC
d(WC, ßMW) = MWSC （蓝色表示出现过的状态）
d(WC, ßM) = MWC
d(WSC, ßM) = MWSC
d(MWC, àMW) = C
d(MWC, àMC) = W
d(MWC, àM) = WC
d(C, ßMW) = MWC
d(C, ßMS) = MSC
d(C, ßM) = MC
d(W, ßMS) = MWS
d(W, ßMC) = MWC
d(W, ßM) = MW
d(MSC, àMS) = C
d(MSC, àMC) = S
d(MSC, àM) = SC
d(MWS, àMW) = S
d(MWS, àMS) = W
d(MWS, àM) = WS
d(S, ßMW) = MWS
d(S, ßMC) = MSC
d(S, ßM) = MS
d(MS, àMS) = e 终态！
d(MS, àM) = S
状态转换序列：MWSC→WC→MWC→C→MSC→S→MS→e
动作序列：àMS，ßM，àMW，ßMS，àMC，ßM，àMS

（陈）12 将下面DFA最小化

解：
初始划分：{0, 1}, {2, 3, 4, 5}
a
{2, 3, 4, 5}——{2, 4}, {3, 5}

（陈）14 构造DFA，它接受S={0, 1}上所有满足如下条件的符号串：每个1都有0直接跟在右边。

（陈）17 下面符号串集合是否为正规集？若是，写出正规式，否则，给出证明
a) L1 = {anbn | n >= 0}
解：不是正规集，证明见讲义4-1第51页

b) L2 = {x | x中含有相同个数的a和b}
解：不是正规集，证明类似a)

c) L3 = {ap | p为素数}
解：不是正规集
证明：假设L3是正规集，对应DFA D的状态数为k。
令p0、p1、…、pk为前k+1个素数，
s0、s1、…、sk为D读入ap0、ap1、…apk后到达的状态。
显然，必有0<=i<j<=k，si、sj为同一状态，且必然是终态，用s表示它。
因此，sàs存在一条长度为pj - pi的路径，每条边标记为a。
在读入apj后，重复此路径(pi – 1)次，得到的符号串t包含a的个数为
pj + (pj – pi) * (pi – 1) = pj * pi – pi * (pi – 1) = pi * (pj - pi + 1)
而pj – pi + 1 > 1，因此pi * (pj - pi + 1)为合数。
D接受t，但t不是L3中符号串，矛盾。
因此，L3不是正规集。