形式语言与自动机Chapter 3 练习参考解答 

Chapter 3 练习参考解答

Exercise 3.1.1 写出下列语言的正规表达式:

c) The set of strings of 0’s and 1’s with at most one pair of consecutive 1’s.

c) 最多包含两个相继的1 的所有 0， 1 字符串的集合. 参考解答：该题的翻译有二义性（Sorry）.

1） 按原题意的解法

对不包含相继的1的所有0， 1 字符串的集合，正规表达式可以为： 1*（0+01）* 或 （0+10）*1*； 包含最多一对相继的1，正规表达式可以为： （0+10）*11（0+01）*；

所以，结果正规表达式可以为：1*（0+01）* + （0+10）*11（0+01）* 2）

若理解为11可以出现多次的解法

正规表达式可以为：

1*（0+01+011）* 或 （0+10+110）*1*； 等等

Exercise 3.1.2 写出下列语言的正规表达式:

b) 0 的个数能够被 5 整除的所有0， 1 字符串的集合. 参考解答：该题问题不多.

正规表达式可以为：（1*01*01*01*01*01*）* Exercise 3.2.1

c) 给出所有正规表达式 R(i2j) , 并尽可能简化之. d) 给出该自动机的语言的一个正规表达式.

参考解答：该题问题反映较多的是关于正规表达式的简化. 本科程较侧重原理，

技术方面不够细致，因此对于“最简“的正规表达式没有作明确的规定，也没有类似于命题演算中有关”范式“的讨论. 同学们在做题时除了应用有关定律外，还可以自己总结出一些规律，比如一个表达式的语言R是另一个表达式S所代表语言的一个子集，则对于R+S就可以消去R，例如 ?+1* 可以简化为 1*. 再如，在已做过的习题中出现的公式，例如Exercise3.4.1(g)，我们可以验证 (?+R)*= R*， 因此 （?+1）* 可以简化为 1*.

综合已阅过的作业，推荐以下结果：

c) R(121) = 1*+1*0 (?+11*0)*11* = 1*+1*0(11*0)*11*

R(122) = 1*0+1*0 (?+11*0)* (?+11*0) = 1*0(11*0)* R(123) = ? +1*0 (?+11*0)*0 = 1*0(11*0)*0 R(221) = 11* + (?+11*0) (?+11*0)*11* = (11*0)*11* R(222) = ?+11*0 + (?+11*0) (?+11*0)* (?+11*0) = (11*0)* R(223) = 0 + (?+11*0) (?+11*0)*0 = (11*0)*0 R(321) = ? + 1 (?+11*0)*11* =1(11*0)*11* R(322) = 1 + 1 (?+11*0)* (?+11*0) =1(11*0)* R(323) = ? + 0 + 1 (?+11*0)* 0 = ? + 0 + 1(11*0)*0 d) 该自动机的语言的一个正规表达式为

R(133) =1*0(11*0)*0 +1*0(11*0)*0 (? + 0 + 1(11*0)*0)* (? + 0 + 1(11*0)*0)

= 1*0(11*0)*0 (0 + 1(11*0)*0)*

Exercise 3.2.3 使用状态消去技术，将如下 DFA 转化为一个正规表达式. 参考解答：该题问题不多，状态消去的次序不同，结果形式上可能有所不同，但相互之间是等价的. 以下是一个解法：

原状态图：

1Startp001q

s01r01消去状态 q：

011Startp000s11110r0

消去状态 r：

1Startp000+10*10

01+10*11s

消去状态 s：

1+0(01+10*11)*(00+10*10)Startp

结果正规表达式可以为：(1+0(01+10*11)*(00+10*10))*

Exercise 3.2.4 将下列正规表达式转化为带e-转移的NFA.

b) (0+1)01c) 00(0+1)*参考解答：若严格按照所介绍的算法构造，则结果如下：

b)

0? ? ? ? Start1? 0? 1

c)

Start0? 0? ? ? 0? ? ? ? 1? ?

Exercise 3.4.1 验证下列包含正规表达式的等式c) (RS) T = R (ST) .g) (?+R)* = R*. 参考解答：

c) 将两个表达式具体化，将R替换为a，将S替换为b.

(RS)T具体化为(ab)a，R(ST)具体化为a(ba)，而L((ab)a)=L(a(ba))={abc}，所以原等式成立；

g) 将两个表达式具体化，将R替换为a.

(?+R)*具体化为(?+a)*，R*具体化为a*，而L((?+a)*)=L(a*)={?,a,aa,aaa,…}，（注：严格证明L((?+a)*)=L(a*)，可以在归纳证明：对任意k>=0，{?，a}k={a}k的基础上进行），所以原等式成立；

Exercise 3.4.2 证明或否证下列关于正规表达式的命题b) (RS+R)*R = R (SR+R)* .d) (R+S)*S = (R*S)*. 参考解答：

b) 将两个表达式具体化，将R替换为a，将S替换为b.

(RS+R)*R具体化为(ab+a)*a，R (SR+R)*具体化为a(ba+a)*，可以证明L((ab+a)*a)=L(a(ba+a)*) （注：同上，可以先归纳证明：

对任意k>=0，{ab，a}k{a}={a}{ba，a}k，而由连接运算对?运算的分配律，可知 L((ab+a)*a)=?k=0,1,2,…({ab，a}k{a}), L(a(ba+a)*)=?k=0,1,2,…({a}{ba，a}k)，由此证得L((ab+a)*a)=L(a(ba+a)*)

），

所以原等式成立；

g) 将两个表达式具体化，将R替换为a，将S替换为b.

(R+S)*S具体化为(a+b)*b，(R*S)*具体化为(a*b)*，由于??L((a*b)*)，而

??L((a*b)*)，所以原等式不成立.