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

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

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

1.写出表示下列语言的正则表达式。 (吴贤珺 02282047) ⑴ {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页

你可能喜欢

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

热门文档

相关文档

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