形式语言与自动机理论(第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*))*,
形式语言与自动机理论-蒋宗礼-第一章参考答案_工学_高等教育_教育专区。形式语言与自动机理论(第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 蒋宗礼 课程目的和基本要求 ? ...
热门文档