形式语言第四章参考答案蒋宗礼.docx
- 文档编号:15402778
- 上传时间:2023-07-04
- 格式:DOCX
- 页数:15
- 大小:122.33KB
形式语言第四章参考答案蒋宗礼.docx
《形式语言第四章参考答案蒋宗礼.docx》由会员分享,可在线阅读,更多相关《形式语言第四章参考答案蒋宗礼.docx(15页珍藏版)》请在冰点文库上搜索。
形式语言第四章参考答案蒋宗礼
1.写出表示下列语言的正则表达式。
{0,1}*。
解:
所求正则表达式为:
(0+1)*。
{0,1}+。
解:
所求正则表达式为:
(0+1)+。
{x│x∈{0,1}+且x中不含形如00的子串}。
解:
根据第三章构造的FA,可得所求正则表达式为:
1*(01+)*(01+0+1)。
{x│x∈{0,1}*且x中不含形如00的子串}。
解:
根据上题的结果,可得所求正则表达式为:
ε+1*(01+)*(01+0+1)。
{x│x∈{0,1}+且x中含形如10110的子串}。
解:
所求正则表达式为:
(0+1)*10110(0+1)*。
{x│x∈{0,1}+且x中不含形如10110的子串}。
解:
根据第三章的习题,接受x的FA为:
要求该FA对应的正则表达式,分别以q0、q1、q2、q3、q4为终结状态考虑:
q0为终态时的正则表达式:
(0*(11*0(10)*(ε+111*11*0(10)*)0)*)*
q1为终态时的正则表达式:
0*1(1*(0(10)*111*1)*(0(10)*00*1)*)*
q2为终态时的正则表达式:
0*11*0((10)*(111*11*0)*(00*11*0)*)*
q3为终态时的正则表达式:
0*11*0(10)*1(11*11*0((10)*(00*11*0)*)*1)*
q4为终态时的正则表达式:
0*11*0(10)*11(1*(11*0((00*11*0)*(10)*)*11)*)*
将以上5个正则表达式用“+”号相连,就得到所要求的正则表达式。
{x│x∈{0,1}+且当把x看成二进制数时,x模5与3同余和x为0时,│x│=1
且x≠0时,x的首字符为1}。
解:
先画出状态转移图,设置5个状态q0、q1、q2、q3、q4,分别表示除5的余数是0、1、2、3、4的情形。
另外,设置一个开始状态q.由于要求x模5和3同余,而3模5余3,故只有q3可以作为终态。
由题设,x=0时,│x│=1,模5是1,不符合条件,所以不必增加关于它的状态。
下面对每一个状态考虑输入0和1时的状态转移。
q:
输入1,模5是1,进入q1。
q0:
设x=5n。
输入0,x=5n*2=10n,模5是0,故进入q0
输入1,x=5n*2+1=10n+1,模5是1,故进入q1
q1:
设x=5n+1。
输入0,x=(5n+1)*2=10n+2,模5是2,故进入q2
输入1,x=(5n+1)*2+1=10n+3,模5是3,故进入q3
q2:
设x=5n+2。
输入0,x=(5n+2)*2=10n+4,模5是4,故进入q4
输入1,x=(5n+2)*2+1=10n+5,模5是0,故进入q0
q3:
设x=5n+3。
输入0,x=(5n+3)*2=10n+6,模5是1,故进入q1
输入1,x=(5n+3)*2+1=10n+7,模5是2,故进入q2
q4:
设x=5n+4。
输入0,x=(5n+4)*2=10n+8,模5是3,故进入q3
输入1,x=(5n+4)*2+1=10n+9,模5是4,故进入q4
则状态转移图如下:
则所求的正则表达式为:
1(010*1+(1+001*0)(101*0)*(0+110*1))*(1+001*0)(101*0)*
{x│x∈{0,1}+且x的第10个字符是1}。
解:
所求正则表达式为:
(0+1)91(0+1)*。
{x│x∈{0,1}+且x以0开头以1结尾}。
解:
所求正则表达式为:
0(0+1)*1。
{x│x∈{0,1}+且x中至少含两个1}。
解:
所求正则表达式为:
(0+1)*1(0+1)*1(0+1)*。
{x│x∈{0,1}*和如果x以1结尾,则它的长度为偶数;如果x以0结尾,则它的长度为奇数}。
解:
所求正则表达式为:
(0+1)2n+11+(0+1)2n0(n∈N)
或0+(0+1)((0+1)(0+1))*1+(0+1)(0+1)((0+1)(0+1))*0。
{x│x是十进制非负实数}。
解:
首先定义∑={.,0,1,2,3,4,5,6,7,8,9}
则所求正则表达式为:
(0+1+…+9)*.(0+1+…+9)*。
Φ。
解:
所求正则表达式为:
Φ。
{ε}。
解:
所求正则表达式为:
ε。
*********************************************************************************
2.理解如下正则表达式,说明它们表示的语言
(1)(00+11)+表示的语言特征是0和1都各自成对出现
(2)(1+0)*0100+表示的语言特征是以010后接连续的0结尾
(3)(1+01+001)*(ε+0+00)表示的语言特征是不含连续的3个0
(4)((0+1)(0+1))*+((0+1)(0+1)(0+1))*表示所有长度为3n或2m的0,1串(n≥0,m≥0)
(5)((0+1)(0+1))*((0+1)(0+1)(0+1))*表示所有长度为3n+2m的0,1串(n≥0,m≥0)
(6)00+11+(01+10)(00+11)*(10+01)表示的语言特征为长度为偶数n的串.当n=2时,是00或11的串。
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总可以找到一组x1x2x3使得x=x1x2x3其中x3∈tx1x2∈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)+tx∈(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)总可以找到x1x2使得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且总可以找到一组x1x2使得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总可以找到x1x2使得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且总可以找到一组x1x2使得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
(6)乘法运算单位元:
rε=εr=r
证明:
∵对∀x∈Rxε=εx=x
∴R{ε}={ε}R=R
∴rε=εr=r
(7)乘法运算零元素:
r∅=∅r=∅
证明:
∵对∀x∈Rx∅=∅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)kr=r(sr+r)k成立,则(r+rs)*r=r(sr+r)*肯定成立
可以用归纳法证明(r+rs)kr=r(sr+r)k对所有的k>=0成立
I.k=0时候,(r+rs)0r=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)nr(r+sr)=r(sr+r)n(r+sr)
=r(sr+r)n(sr+r)=r(sr+r)n+1
这就是说,结论对k=n+1成立,即证明了(r+rs)kr=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*))*,
L((r+s)*)
L((r*s*)*),所以(r+s)*
(r*s*)*
II.(r+s)*=((r+s)*)*,
对任意m,n>=0,rmsn
(r+s)m+n,所以r*s*
(r+s)*
(r*s*)*
((r+s)*)*=(r+s)*
由I,II可以知道(r*s*)*
(r+s)*,(r+s)*
(r*s*)*
得到(r+s)*=(r*s*)*
(6)(r+s)*=r*+s*
不成立,假设r,s分别是表示语言R,S的正则表达式,例如当R={0},S={1},L((r+s)*)={x|x=
或者x是所有由0,1组成的字符串}
L(r*+s*)=L(r*)
L(s*)={
0,00,000,……}
{
1,11,111,……}
L((r+s)*)
L(r*+s*),例如10
L((r+s)*),10
L(r*+s*)
**********************************************************************************************
5.构造下列正则表达式的等价FA吴丹02282090
*********************************************************************************
6、构造等价于下图所示DFA的正则表达式。
仅给出
(2)的构造过程
(1)
与他等价的正则表达式为:
ε+(01+1)(01+10+11(01+1))*
(2)
答案(之一):
(01+(1+00)((1+00*1)0)*((1+00*1)1))*(ε+(1+00)((1+00*1)0)*00*)
预处理:
去掉q3:
去掉q1:
去掉q2:
去掉q0:
(3)
((0+10)*11)(01+(1+00)(0+10)*11)*(0+(1+00)(0+10)*1)+(0+10)*1
(4)
((0+11+10(0+1))((01)*+(00(0+1))*)*1)*(1+10+ε+(0+11+10(0+1))((01)*+(00(0+1)*)*)(00+0+ε))
*******************************************************************************************
7.整理不同模型等价证明的思路
解:
正则语言有5种等价的描述模型:
正则文法(RG)、确定的有穷状态自动机(DFA)、不确定的有穷状态自动机(NFA)、带空移动的有穷状态自动机(
)、正则表达式(RE)。
这5种等价模型的转换关系可以用下图表示:
(1)
RG分为右线性文法和左线性文法。
对于右线性文法,只需要采用模拟M的移动即可
,
M的开始符号就是G的开始符号。
而对于左线性文法,G用规约模拟M的移动:
新增加的符号Z为G的识别符号,也就是开始符号。
(2)
同上,分为右线性和左线性文法。
对于右线性文法:
其中,G的开始符号为M的开始符号,新增的状态Z为M的终止状态。
对于左线性文法:
增加Z为M的开始状态;对应形如
的产生式,定义
;对应形如
的产生式,定义
;G的开始符号为M的终止状态。
(3)
采用图上作业法:
预处理:
标记X、Y的状态为标记状态,删除不可达状态;
并弧:
用从q到p的、标记为r1+r2……rg的弧取代q到p的标记为r1,r2……的并行弧。
去状态:
如果从q到p有一条标记为r1的弧,从p到t有一条标记为r2的弧,不存在从状态p到状态p的弧,将状态p和与之关联的这两条弧去掉,用一条从q到t的标记为r1r2的弧代替;如果从q到p有一条标记为r1的弧,从p到t有一条标记为r2的弧,从状态p到状态p标记为r3的弧,将状态p和与之关联的这三条弧去掉,用一条从q到t的标记为r1r3*r2的弧代替;如果图中只有三个状态,而且不存在从标记为X的状态到达标记为Y的状态的路,则将除标记为X的状态和标记为Y的状态之外的第3个状态及其相关的弧全部删除。
处理:
从标记为X的状态到标记为Y的状态的弧的标记为所求的正则表达式。
如果此弧不存在,则所求的正则表达式为Φ。
(4)
由于NFA也是一个特殊的
,则其转化可以参考
(5)
(6)
:
确定化
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 形式语言 第四 参考答案 蒋宗礼
![提示](https://static.bingdoc.com/images/bang_tan.gif)