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

第6789章作业及参考答案

第6789章作业及参考答案_第1页
1/12
第6789章作业及参考答案_第2页
2/12
第6789章作业及参考答案_第3页
3/12
第6 章P231: 1、构造产生下列语言的CFG (2) {1n02m1n |n,m≥1} 解:需保证1 的个数相等且0 的个数为偶数 S1S1|1A1 A00A|00 (4)含有相同个数的0 和1 的所有0、1 串 S0AS|1BS|ε A1|0AA B0|1BB 错解1: S10S|01S|10|01|ε 错解2: S1S0|0S1|1A0|0A1, A10|01|ε (推不出 0110) 错解3: S10S|1S0|S10|01S|0S1|S01|ε (推不出 00111100) 讨论: 不能限制 0 和1 必须在同一次推导中都出现 15、构造与下列文法(原题中去 产生式后的文法)等价的CNF Sa|b|aB|aBB|bA|bAA Baa|aB|Ba|aBa Abb|bbA 解:第一步 Sa|b|BaB|BaBB|BbA|BbAA BBaBa|BaB|BBa|BaBBa ABbBb|BbBbA Baa Bbb 第二步 Sa|b|BaB|BaB1|BbA|BbA1 BBaBa|BaB|BBa|BaB2 ABbBb|BbB3 Baa Bbb B1BB A1AA B2BBa B3BbA 讨论: 这种题需要将步骤写清, 意义在于机械化这种事情是我们的目标, 你不必加入太多自己的智慧. Ba和Ba的区别? 第7 章 P257: 1、构造识别下列语言的PDA (2) L = {1n02m1n|n,m≥1} 要求  用两种方法做  用七元组表示  用推广的状态转换图表示 解法 1:先构造产生该语言的GNF 文法,再由文法推导的启示或依定理 7-3 的构造方法,设计出 PDA 构造出产生该语言的CFG S1S1|1B1 B00B|00 得到对应的GNF: S1SA|1BA A1 B0C|0CB C0 构造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,m≥ 1} 用推广的状态转换图如右所示: 提示,还可以仿照书中例题,加入终止状态qf 及初始栈符号Z, 使 N(M1)= L(M1)={1n02m1n|n,m≥1}, 注意: 如果要这样做, 请加适当的说明 解法1 拓展(2005 级崔卫华的想法):问能否把GNF 中Aa 中的a 用作00 思考: 崔同学实际是想设计接受{1nam1n|n,m≥1}的PDA 以简化, 但又没有底气 这种想法很大胆(褒义的"大胆") 也是可行的. 过程是: 先设计PDA 接受L={1nam1n|n,m≥1} 这儿={1,a} 构造代换f: f(1)=1, f(a)=00, 则f(L)就是我们要的={1,0} 上的语言, PDA随之而定 只是未向同学们介绍如何利用代换设计PDA 解法2 之一:可以将 PDA 的工作分为3 个阶段: (1...

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

碎片内容

第6789章作业及参考答案

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