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

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的所有0， 1 字符串的集合，正规表达式可以为： 1*（0+01）* 或 （0+10）*1*； 包含最多一对相继的1，正规表达式可以为： （0+10）*11（0+01）*； 所以，结果正规表达式可以为：1*（0+01）* + （0+10）*11（0+01）* 若理解为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 转化为一个正规表达式. （图略） 参考解答：该题问题不多，状态消去的次序不同，结果形式上可能有所不同，但相互之间是等价的. 以下是一个解法： 原状态图： 消去状态 q： 消去状态 r： 消去状态 s： 结果正规表达式可以为：(1+0(01+10*11)*(00+10*10))* Exercise 3.2.4 将下列正规表达式转化为带(-转移的NFA. b) (0+1)01 c) 00(0+1)* 参考解答：若严格按照所介绍的算法构造，则结果如下： b) c) 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 证明或否证下列关于正规表