文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 工学 > 形式语言与自动机理论-蒋宗礼-第四章参考答案
侵权投诉

形式语言与自动机理论-蒋宗礼-第四章参考答案

形式语言与自动机理论(第2版),清华大学出版社 北京工业大学计算机学院蒋宗礼老师主编

(6) 乘法运算单位元:rε=εr=r 证明:∵对 x R x = x=x ∴R{ }={ }R=R ∴r = r=r

(7)乘法运算零元素:r = r= 证明:∵对 x R x = x= ∴R{ }={ }R=R ∴r = r= (8) *=ε

证明 *= 0∪ 1∪ 2∪ 3…...=ε∪ 1∪ 2∪ 3…...=ε (9) (r+ε)*=r*

由第一章的作业1.30中的第九题 (L1∪{ε})*=L1*其中L1为正则语言

又r为正则表达式 正则语言可以用正则表达式表示,因此显然有(r+ε)*=r*成立 (10) (r*s*)*=(r+s)*

由第一章的作业1.30中的第八题 (L2∪L1)*=( L2* L1*)* 其中L1、L2 为正则语言

又r、s为正则表达式 正则语言可以用正则表达式表示,因此显然有(r+s)*= (r*s*)*成立 即(r*s*)*=(r+s)*成立 (11) (r*)*=r*

由第一章的作业1.30中的第三题 (L1*)*= L1*其中L1为正则语言

又r为正则表达式 正则语言可以用正则表 达式表示,因此显然有(r*)*= r*成立

*********************************************************************************

4下面各式成立吗?请证明你的结论 (1) (r+rs)*r=r(sr+r)* 证明:成立。

如果对所有的k>=0, (r+rs)k r=r(sr+r)k 成立,则(r+rs)*r=r(sr+r)*肯定成立 可以用归纳法证明(r+rs)k r=r(sr+r)k对所有的k>=0成立 I. k=0时候,(r+rs)0 r=r= r(sr+r)0 II. 假设k=n时候(r+rs)nr=r(sr+r)n成立,往证k=n+1时候结论成立 (r+rs)n+1r=(r+rs)n (r+rs)r=(r+rs)n (rr+rsr)= (r+rs)n r (r+sr)= r(sr+r)n (r+sr) = r(sr+r)n (sr+r)= r(sr+r)n+1

这就是说,结论对k=n+1成立,即证明了(r+rs)k r=r(sr+r)k对所有的k>=0成立,所以(r+rs)*r=r(sr+r)* (2) t(s+t)r=tr+tsr

证明:不成立。不妨取r=0,s=1,t=2,则t(s+t)r=2(1+2)0=210+230,但tr+tsr=20+210. (3) rs=sr

证明:不成立。不妨取r=0,s=1,显然rs=01,而sr=10. (4) s(rs+s)*r=rr*s(rr*s)*

不成立,假设r,s分别是表示语言R,S的正则表达式,例如当R={0},S={1}, L(s(rs+s)*r)是以1开头的字符串,而L(rr*s(rr*s)*)是以0开头的字符串.L(s(rs+s)*r) L(rr*s(rr*s)*) 所以s(rs+s)*r rr*s(rr*s)*,结论不成立 (5)(r+s)*=(r*s*)* 证明:结论成立。

I. L(r+s)=L(r) L(s), L(r)=L(rs0) L(r*s*), L(s)=L(r0s) L(r*s*) 那么L(r+s)=L(r) L(s) L(r*s*),(L(r+s))* (L(r*s*))*,

上一页第4页

你可能喜欢

  • 形式语言与自动机答案
  • 自动机与自动线
  • 细胞自动机
  • 3d试机号
  • 形式语言与自动机理论

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email