电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本
换一换
首页 金锄头文库 > 资源分类 > DOC文档下载
分享到微信 分享到微博 分享到QQ空间

第6789章-作业及参考答案

  • 资源ID:145970601       资源大小:139.50KB        全文页数:12页
  • 资源格式: DOC        下载积分:10金贝
快捷下载 游客一键下载
账号登录下载
微信登录下载
三方登录下载: 微信开放平台登录   支付宝登录   QQ登录  
二维码
微信扫一扫登录
下载资源需要10金贝
邮箱/手机:
温馨提示:
快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
如填写123,账号就是123,密码也是123。
支付方式: 支付宝    微信支付   
验证码:   换一换

 
账号:
密码:
验证码:   换一换
  忘记密码?
    
1、金锄头文库是“C2C”交易模式,即卖家上传的文档直接由买家下载,本站只是中间服务平台,本站所有文档下载所得的收益全部归上传人(卖家)所有,作为网络服务商,若您的权利被侵害请及时联系右侧客服;
2、如你看到网页展示的文档有jinchutou.com水印,是因预览和防盗链等技术需要对部份页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有jinchutou.com水印标识,下载后原文更清晰;
3、所有的PPT和DOC文档都被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;下载前须认真查看,确认无误后再购买;
4、文档大部份都是可以预览的,金锄头文库作为内容存储提供商,无法对各卖家所售文档的真实性、完整性、准确性以及专业性等问题提供审核和保证,请慎重购买;
5、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据;
6、如果您还有什么不清楚的或需要我们协助,可以点击右侧栏的客服。
下载须知 | 常见问题汇总

第6789章-作业及参考答案

第6章P231:1、构造产生下列语言的CFG(2) 1n02m1n |n,m1解:需保证1的个数相等且0的个数为偶数S1S1|1A1A00A00(4)含有相同个数的0和1的所有0、1串S0AS1BSA1|0AAB0|1BB错解1: S10S01S1001错解2: S1S00S11A00A1, A1001 (推不出0110)错解3: S10S1S0S1001S0S1S01 (推不出00111100)讨论: 不能限制0和1必须在同一次推导中都出现 15、构造与下列文法(原题中去e产生式后的文法)等价的CNFSa|b|aB|aBB|bA|bAABaa|aB|Ba|aBaAbb|bbA解:第一步Sa|b|BaB|BaBB|BbA|BbAABBaBa|BaB|BBa|BaBBaABbBb|BbBbABaaBbb第二步Sa|b|BaB|BaB1|BbA|BbA1BBaBa|BaB|BBa|BaB2ABbBb|BbB3BaaBbbB1BBA1AAB2BBaB3BbA讨论: 这种题需要将步骤写清, 意义在于机械化这种事情是我们的目标, 你不必加入太多自己的智慧. Ba和Ba的区别?第7章 P257:1、构造识别下列语言的PDA(2) L = 1n02m1n|n,m1要求l 用两种方法做l 用七元组表示l 用推广的状态转换图表示解法1:先构造产生该语言的GNF文法,再由文法推导的启示或依定理7-3的构造方法,设计出PDA构造出产生该语言的CFGS1S1|1B1B00B00得到对应的GNF:S1SA|1BAA1B0C|0CBC01,S/SA1,S/BA1,A/0,B/C0,B/CB0,C/q构造PDA M1=(q,0,1,S,A,B,C, 1, q, S, )其中1为:1(q, 1, S)=(q, SA), (q, BA)1(q, 1, A)=(q, ) 1(q, 0, B)=(q, C), (q, CB) 1(q, 0, C)=(q, ) 有N(M1)= 1n02m1n|n,m1用推广的状态转换图如右所示:提示,还可以仿照书中例题,加入终止状态qf及初始栈符号Z, 使N(M1)= L(M1)=1n02m1n|n,m1, 注意: 如果要这样做, 请加适当的说明解法1拓展(2005级崔卫华的想法):问能否把GNF中Aa中的a用作00思考: 崔同学实际是想设计接受1nam1n|n,m1的PDA以简化, 但又没有底气这种想法很大胆(褒义的大胆)也是可行的.过程是: 先设计PDA接受L=1nam1n|n,m1 这儿=1,a构造代换f: f(1)=1, f(a)=00, 则f(L)就是我们要的D=1,0上的语言, PDA随之而定只是未向同学们介绍如何利用代换设计PDA解法2之一:可以将PDA的工作分为3个阶段:(1)接受1并记载的阶段;(2)接受偶数个0的阶段;(3)匹配1的阶段设q0为开始状态,q1为接受1并记载的阶段,Z0为初始栈符号2(q0, 1, Z0)=(q1,AZ0)2(q1, 1, A)=(q1,AA)q1状态下读入0将进入接受0的状态q22(q1, 0, A)=(q2,BA)为了接受偶数个0,可设q3状态用于接受第2个0,这时只要将进入q2状态时压入的B出栈即可, q3状态下读入0的情形同q1状态下读入0时的情形2(q2, 0, B)=(q3, )2(q3, 0, A)=(q2,BA)在q3状态下读入1且栈顶是A时,进入对1的匹配阶段2(q3, 1, A)=(q4, )q3状态下继续进入1和A的匹配2(q4, 1, A)=(q4, )正确的匹配应是q3状态下读完所有的符号,且栈中只余Z02(q4, , Z0)=(q5, )综上,设计的PDA为:M2=(q0, q1, q2, q3, q4, q5,0,1,A,B,Z0, 2, q0, Z0, q5)有L(M2)=N(M2) = L0,A/BAq0q1q2q3q4q51,Z0/ AZ01,A/ AA0,A/BA0,B/1,A/1,A/,Z0/用推广的状态转换图如下所示:解法2之二:可以将PDA的工作分为3个阶段:(1)接受1并记载的阶段;(2)接受偶数个0的阶段;(3)匹配1的阶段设q0为开始状态,q1为接受1并记载的阶段,Z0为初始栈符号2(q0, 1, Z0)=(q1,AZ0)2(q1, 1, A)=(q1,AA)q1状态下读入0将进入接受0的状态q2, 用栈符号B记忆2(q1, 0, A)=(q2,BA)q2状态读入0且栈顶为B, 这时一定是第偶数个0, B被匹配, B出栈2(q2, 0, B)=( q2, )q2状态读入0且栈顶为A, 这时已经出现过偶数个0, 这个零为第奇数个0, 将B压栈2(q2, 0, A)=(q2,BA)在q2状态下读入1且栈顶是A时,进入对1的匹配阶段2(q2, 1, A)=(q3, )q3状态下继续进入1和A的匹配2(q3, 1, A)=(q3, )正确的匹配应是q3状态下读完所有的符号,且栈中只余Z02(q3, , Z0)=(q4, )综上,设计的PDA为:M2=(q0, q1, q2, q3, q4 ,0,1,A,B,Z0, 2, q0, Z0, q4)有L(M2)=N(M2) = L解法2之三(采纳2005级岳宝的思路, 贺利坚改正并整理):M2=(q0, q1, qf,0,1,A,B,Z0, 2, q0, Z0, qf)在记忆阶段, 用A记忆读入的0, B记忆读入的1, 则有:2(q0, 1, Z0)=(q0,BZ0)2(q0, 1, B)=(q0,BB)2(q0, 0, B)=(q0,AB)2(q0, 0, A)=(q0,AA)设计不确定的PDA, 由记忆阶段转到匹配阶段:2(q0, , A)=(q1,A)匹配阶段的工作, 再匹配的0的个数与栈中A的个数必相等, 即0必为偶数个:2(q1, 0, A)=(q1, ) ; 匹配阶段, 再匹配的1的个数与栈中B的个数必相等:2(q1, 1, B)=(q1, ) ; 进入终态:2(q1, , Z0)=(q2, ) ; 这样, 有L(M2)=N(M2) = L解法2之四 (2005级孙磊提供, 贺利坚加说明):将L看作两部分, 前面部分为1n0m, 后面部分为0m1nM2=(q0, q1, qf,0,1,A,B,Z0, 2, q0, Z0, qf)其中: q0: 处理句子的前半部分q1: 处理句子的后半部分qf: 终止状态 (1) 在q0状态时先接受1并将B压入栈2(q0, 1, Z0)=(q0,BZ0)2(q0, 1, B)=(q0,BB)(2) 在q0状态栈顶为B时接受一个0, 首先要将A压栈以记忆2(q0, 0, B)=(q0,AB)(3) 在q0状态栈顶为A时接受一个0, 可能是前半部分的0需要记忆, 也可能是后半部分的0需要匹配2(q0, 0, A)=(q0,AA), (q1, )(注意不定义2(q0, 1, A)(4)在q1状态下对读入的0和1逐个地进行匹配2(q1, 0, A)=(q1, )2(q1, 1, B)=(q1, )(5)当栈中只留Z0时, 清栈且进入终止状态2(q1, , Z0)=(qf, )这样, 有L(M2)=N(M2) = L解法2之四 (2006级的“集体智慧”,贺利坚完善):M2=(q0, q1, q2, qf,0,1,A,B1, B2,Z0, 2, q0, Z0, qf) (1) q0状态:在读入0之前,记载1的个数,每读入一个1,在栈中压入符号A2(q0, 1, Z0)=(q1,AZ0)2(q1, 1, A)=(q1,AA)(2) 在读到0后,0的个数为偶数个,第奇数个0,压入栈符号B1,第偶数个0时,用栈符号B2取代B1。2(q1, 0, A)=(q1, B1A)2(q1, 0, B1)=(q1, B2)2(q1, 0, B2)=(q1, B1)2(q1, 1, B2)=(q2, )(3) 在q2状态,匹配12(q2, 1, A)=(q2, )2(q2, , Z0)=(qf, )有L(M2)=N(M2) = L本题主要存在的问题:(1)不写解题过程的说明, 无法看清思路(考试中会强调一定要写过程)(2)不写清接受方式: 以空栈方式接受或以终止状态接受或二者均可(3)未画状态转移图(布置时有这一要求)8、构造与下列文法等价的PDA (1)SaBB|bAA, BaBB|aA|a, AbBA| b解:(根据定理7-3证明中提供的构造方法完成)有PDA M= (q,a,b,S,A,B , , q, S, ) (q, a, S)=(q, BB) (q, b, S)=(q, AA) (q, a, B)=(q, BB), (q, A), (q, ) (q, b, A)=(q, BA),(q, ) 从而N(M)=L(G) -一定要点出接受方式是以空栈方式接受主要问题(1)不按定理的方法构造:PDA M= (p, q,a,b,S,A,B , , q, S, )!学会机械化的构造方法如果另起炉灶(鼓励这样做, 唯有此才能前进, 才能进步, 这也是终极目标), 但要先有前期工作.不能突然而至, 似有照猫画虎嫌疑, 结果不猫不虎. (2) 按教材上的原题做: SaBB|bAA, BaBB|aA|a, AbBA|有PDA M= (q,a,b,S,A,B , , q, S, ) (q, a, S)=(q, BB) (q, b, S)=(q, AA) (q, a, B)=(q, BB), (q, A), (q, ) (q, b, A)=(q, BA) (q, , A)=(q, ) 从而N(M)=L(G)错误!原因: 给出的CFG是GNF吗? 这能保证这一点, 不能这么做.按原题的正确做法是:首先, L(G)消除文法SaBB|bAA, BaBB|aA|a, AbBA|中的空产生式, 并转换为等价的GNF, 有SaBB|bAA|bA|b, BaBB|aA|a, AbB

注意事项

本文(第6789章-作业及参考答案)为本站会员(日度)主动上传,金锄头文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即阅读金锄头文库的“版权提示”【网址:https://www.jinchutou.com/h-59.html】,按提示上传提交保证函及证明材料,经审查核实后我们立即给予删除!

温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.