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

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

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

n 4时,是以01或10开头,中间的子串00或11成对出现,最后以10或01结尾的串

********************************************************************************************* 4.3.证明下列各式 褚颖娜 02282072

(1)结合律 (rs)t=r(st) (r+s)+t= r+(s+t)

1)证明 对 x∈(rs)t 总可以找到一组x1 x2 x3 使得 x=x1x2x3 其中x3∈t x1x2∈rs 且 x1∈r, x2∈s, 则 x2x3∈st 因此x1(x2x3)∈r(st) 即 x1x2x3∈r(st) x∈r(st)得证 因此 (rs)t r(st)

同理可证r(st) (rs)t 则 (rs)t=r(st) 成立

2) 证明 对 x∈(r+s)+t x∈(r+s)或x∈t 对于x∈r+s x∈r或r∈s , 因此x∈r或x∈s或x∈t x∈r或x∈(s+t) x∈r+(s+t) 所以(r+s)+t r+(s+t)

同理可证r+(s+t) (r+s)+t 则(r+s)+t= r+(s+t) 成立

(2)分配律 r(s+t)=rs+rt (s+t)r=sr+tr

1) 证明 对于 x∈r(s+t) 总可以找到x1 x2 使得x=x1x2 其中x1∈r, x2∈(s+t)

由x2∈(s+t) x2∈s或x2∈t 则x1x2∈rs或x1x2∈rt 所以r(s+t) rs+rt

对于 x∈rs+rt x∈rs或x∈rt 且总可以找到一组x1 x2 使得x=x1x2 其中x1∈r, x2∈s或x1∈r, x2∈t x1∈r,x2∈s或x2∈t x1∈r,x2∈(s+t) x1x2∈r(s+t) 所以rs+rt r(s+t) 则r(s+t)=rs+rt

2) 证明 对于 x∈(s+t)r 总可以找到x1 x2 使得x=x1x2 其中 x1∈(s+t),x2∈r

由x1∈(s+t) x1∈s或x1∈t 则x1x2∈sr或x1x2∈tr 所以(s+t)r sr+tr

对于 x∈sr+tr x∈sr或x∈tr 且总可以找到一组x1 x2 使得x=x1x2 其中x1∈s, x2∈r或x1∈t, x2∈r x1∈s或x1∈t, x2∈r x1∈(s+t) ,x2∈r x1x2∈(s+t)r 所以sr+tr (s+t)r 则(s+t)r=sr+tr

(3)交换律 r+s=s+r

证明 对于 x∈r+s x∈r或x∈s x∈s或x∈r x∈s+r 所以r+s s+r 同理可证s+r∈r+s

则r+s=s+r

(4)幂等律 r+r=r

证明 对于 x∈r+r x∈r或x∈r x∈r 所以r+r r

对于 x∈r x∈r或x∈r x∈r+r 所以r r+r 因此 r+r=r

(5)加法运算零元素:r+ =r

证明 对于 x∈r+ x∈r或x∈ x∈r 所以r+ r

对于 x∈r x∈r或x∈ x∈r+ 所以r r+ 因此 r+ =r

上一页第3页

你可能喜欢

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

热门文档

相关文档

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