电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

形式语言与自动机理论-蒋宗礼-参考答案VIP专享VIP免费

形式语言与自动机理论-蒋宗礼-参考答案_第1页
形式语言与自动机理论-蒋宗礼-参考答案_第2页
形式语言与自动机理论-蒋宗礼-参考答案_第3页
精品文档。1欢迎下载第三章作业答案1.已知 DFA M1与 M2如图 3-18 所示。 (敖雪峰 02282068) (1)请分别给出它们在处理字符串1011001 的过程中经过的状态序列。(2)请给出它们的形式描述。0101001Sq0q1q2q3101100q0q1q2q3101图3- 18 两个不同的 DFA 解答: (1)M1 在处理 1011001的过程中经过的状态序列为q0q3q1q3q2q3q1q3; M2 在处理 1011001的过程中经过的状态序列为q0q2q3q1q3q2q3q1; (2) 考虑到用形式语言表示, 用自然语言似乎不是那么容易, 所以用图上作业法把它们用正则表达式来描述 : M1: [01+(00+1)(11+0)][11+(10+0)(11+0)]* M2: (01+1+000){(01)*+[(001+11)(01+1+000)]*} ******************************************************************************* 2.构造下列语言的DFA ( 陶文婧 02282085 ) (1){0 ,1}*0,1(2){0 ,1}+ 0,10,1S(3){x|x{0 , 1}+且 x 中不含 00 的串 } (设置一个陷阱状态,一旦发现有00 的子串,就进入陷阱状态)精品文档。2欢迎下载11S00100,1(4){ x|x{0 ,1}*且 x 中不含 00 的串 } (可接受空字符串,所以初始状态也是接受状态)11S00100,1(5){x|x{0 , 1}+且 x 中含形如 10110 的子串 } 1S00100,110101(6){x|x{0 , 1}+且 x 中不含形如10110 的子串 } (设置一个陷阱状态,一旦发现有00 的子串,就进入陷阱状态)1S00100,1,10101(7){x|x{0 , 1}+且当把 x 看成二进制时,x 模 5 和 3 同余,要求当x 为 0 时, |x|=1,且x 0 时, x 的首字符为1 } 1.以 0 开头的串不被接受,故设置陷阱状态,当DFA在启动状态读入的符号为0,则进入陷阱状态2.设置 7 个状态:开始状态qs,q 0:除以 5 余 0 的等价类, q1:除以 5 余 1 的等价类 ,q 2:除以5 余 2 的等价类, q3: 除以 5 余 3 的等价类, q4:除以 5 余 4 的等价类,接受状态qt3.状态转移表为状态0 1 q0 q1q2q1q3q2q2q0q4q3q1q2精品文档。3欢迎下载q4q3q411100,10q sq tq 1q 21q 010q 40q 3100(8){x|x{0 ,1}+且 x 的第十个字符为1} (设置一个陷阱状态,一旦发现x 的第十个字符为0,进入陷阱状态)1S0,10,10,10,10,110,0,10,10,10,10,1(9){x|x{0 , 1}+且 x 以 0 开头以 1 结尾 } (设置陷阱状态,当第一个字符为1 时,进入陷阱状态)1S01100,10(10){x|x{0 ,1}+且 x 中至少含有两...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

爱的疯狂+ 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部