形式语言与自动机理论(第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
形式语言与自动机理论-蒋宗礼-第一章参考答案_工学_高等教育_教育专区。形式语言与自动机理论(第2版),清华大学出版社北京工业大学计算机学院蒋宗礼老师主编...
形式语言与自动机理论-蒋宗礼-第三章参考答案_工学_高等教育_教育专区。形式语言与自动机理论(第2版),清华大学出版社北京工业大学计算机学院蒋宗礼老师主编...
形式语言与自动机理论-蒋宗礼-第二章参考答案_工学_高等教育_教育专区。形式语言与自动机理论(第2版),清华大学出版社北京工业大学计算机学院蒋宗礼老师主编...
形式语言与自动机理论--第四章(蒋宗礼) 隐藏>> 形式语言与自动机理论 Formal Languages and Automata Theory 蒋宗礼 课程目的和基本要求 ? 课程性质–技术基础 ...
形式语言与自动机理论(蒋宗礼)_理学_高等教育_教育专区。形式语言与自动机理论(蒋宗礼)课件形式语言与自动机理论 Formal Languages and Automata Theory 蒋宗礼 ...
形式语言与自动机理论--第二章(蒋宗礼)_理学_高等教育_教育专区。形式语言与自动机课件--蒋宗礼形式语言与自动机理论 Formal Languages and Automata Theory 蒋...
形式语言与自动机理论--第六章(蒋宗礼)_物理_自然科学_专业资料。形式语言与自动机理论 Formal Languages and Automata Theory 蒋宗礼 课程目的和基本要求 ? ...
形式语言与自动机理论 Formal Languages and Automata Theory 蒋宗礼 课程目的和基本要求 ? 课程性质–技术基础 ? 基础知识要求–数学分析(或者高等数学),离散数学 ...
形式语言与自动机理论--第五章(蒋宗礼)_工学_高等教育_教育专区。形式语言与自动机课件--蒋宗礼形式语言与自动机理论 Formal Languages and Automata Theory 蒋...
形式语言与自动机理论--第八章(蒋宗礼)_理学_高等教育_教育专区。形式语言与自动机理论 Formal Languages and Automata Theory 蒋宗礼 课程目的和基本要求 ? ...
热门文档