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

形式语言与自动机王柏、杨娟编著课后习题答案VIP专享VIP免费

形式语言与自动机王柏、杨娟编著课后习题答案_第1页
形式语言与自动机王柏、杨娟编著课后习题答案_第2页
形式语言与自动机王柏、杨娟编著课后习题答案_第3页
形式语言与自动机课后习题答案第二章4.找出右线性文法,能构成长度为1 至 5 个字符且以字母为首的字符串。答: G={N,T,P,S}其中 N={S,A,B,C,D} T={x,y} 其中 x∈{所有字母 } y∈{所有的字符 } P 如下 :S→x S→xA A→y A→yB B→y B→yC C→y C→yD D→y6.构造上下文无关文法能够产生L={ω / ω ∈ {a,b}* 且ω 中 a 的个数是 b 的两倍 }答: G={N,T,P,S}其中 N={S} T={a,b} P如下 :S→aab S→aba S→baaS→aabS S→ aaSb S→aSab S→SaabS→abaS S→ abSa S→aSba S→SabaS→baaS S→ baSa S→bSaa S→Sbaa7.找出由下列各组生成式产生的语言(起始符为S)(1) S→SaS S→b(2) S→aSb S→c(3) S→a S→aE E→aS答:( 1) b(ab)n /n ≥0}或者 L={(ba)nb/n ≥0}(2) L={ancbn /n ≥0}(3) L={a2n+1 /n ≥0}第三章1. 下列集合是否为正则集,若是正则集写出其正则式。(1)含有偶数个a 和奇数个 b 的{a,b}* 上的字符串集合(2)含有相同个数a 和 b 的字符串集合(3)不含子串 aba 的{a,b}* 上的字符串集合答:( 1)是正则集,自动机如下aab b b baa(2) 不是正则集,用泵浦引理可以证明,具体见17 题( 2)。偶 a 偶 b偶 a 奇 b奇 a 奇 b奇 a 偶 b(3) 是正则集先看 L’为包含子串aba 的{a,b}* 上的字符串集合显然这是正则集,可以写出表达式和画出自动机。(略)则不包含子串aba 的{a,b}* 上的字符串集合L 是 L’的非。根据正则集的性质,L 也是正则集。4.对下列文法的生成式,找出其正则式(1)G=({S,A,B,C,D},{a,b,c,d},P,S),生成式 P 如下:S→aA S→BA→abS A→bBB→b B→cCC→D D→bBD→d(2)G=({S,A,B,C,D},{a,b,c,d},P,S),生成式 P 如下:S→aA S→BA→cC A→bBB→bB B→ aC→D C→abBD→d答: (1) 由生成式得:S=aA+B ①A=abS+bB ②B=b+cC ③C=D ④D=d+bB ⑤③④⑤式化简消去CD,得到 B=b+c(d+bB)即 B=cbB+cd+b =>B=(cb)*(cd+b) ⑥将②⑥代入①S=aabS+ab(cb)*(cd+b)+(cb)*(cd+b) =>S=(aab)*(ab+ε )(cb)*(cd+b)(2) 由生成式得:S=aA+B ①A=bB+cC ②B=a+bB ③C=D+abB ④D=dB ⑤由③得B=b*a ⑥将⑤⑥代入④C=d+abb*a=d+ab+a ⑦将⑥⑦代入②A=b+a+c(d+b+a) ⑧将⑥⑧代入①S=a(b+a+c(d+ab+a))+b*a=ab+a+acd+acab+a+b*a5.为下列正则集,构造右线性文法:(1){a,b}*(2)以 abb 结尾的由 a...

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

碎片内容

文库响当当+ 关注
实名认证
内容提供者

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

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