第6789章 作业及参考答案

第6789章 作业及参考答案

ID:6734480

大小:170.00 KB

页数:12页

时间:2018-01-23

第6789章 作业及参考答案_第1页
第6789章 作业及参考答案_第2页
第6789章 作业及参考答案_第3页
第6789章 作业及参考答案_第4页
第6789章 作业及参考答案_第5页
资源描述:

《第6789章 作业及参考答案》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第6章P231:1、构造产生下列语言的CFG(2){1n02m1n

2、n,m≥1}解:需保证1的个数相等且0的个数为偶数S®1S1

3、1A1A®00A|00(4)含有相同个数的0和1的所有0、1串S®0AS|1BS|εA®1

4、0AAB®0

5、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、构造与下列文法(原题中去e产生式

6、后的文法)等价的CNFS®a

7、b

8、aB

9、aBB

10、bA

11、bAAB®aa

12、aB

13、Ba

14、aBaA®bb

15、bbA解:第一步S®a

16、b

17、BaB

18、BaBB

19、BbA

20、BbAAB®BaBa

21、BaB

22、BBa

23、BaBBaA®BbBb

24、BbBbABa®aBb®b第二步S®a

25、b

26、BaB

27、BaB1

28、BbA

29、BbA1B®BaBa

30、BaB

31、BBa

32、BaB2A®BbBb

33、BbB3Ba®aBb®bB1®BBA1®AAB2®BBaB3®BbA讨论:这种题需要将步骤写清,意义在于机械化这种事情是我们的目标,你不必加入太多自己的智慧.Ba和Ba的区别?第7章P257

34、:1、构造识别下列语言的PDA(2)L={1n02m1n

35、n,m≥1}要求l用两种方法做l用七元组表示l用推广的状态转换图表示解法1:先构造产生该语言的GNF文法,再由文法推导的启示或依定理7-3的构造方法,设计出PDA构造出产生该语言的CFGS®1S1

36、1B1B®00B|00得到对应的GNF:S®1SA

37、1BAA®1B®0C

38、0CBC®01,S/SA1,S/BA1,A/ε0,B/C0,B/CB0,C/εq构造PDAM1=({q},{0,1},{S,A,B,C},δ1,q,S,Φ)其中δ1为:δ1(q,1,S)={(q,SA),

39、(q,BA)}δ1(q,1,A)={(q,ε)}δ1(q,0,B)={(q,C),(q,CB)}δ1(q,0,C)={(q,ε)}有N(M1)={1n02m1n

40、n,m≥1}用推广的状态转换图如右所示:提示,还可以仿照书中例题,加入终止状态qf及初始栈符号Z,使N(M1)=L(M1)={1n02m1n

41、n,m≥1},注意:如果要这样做,请加适当的说明解法1拓展(2005级崔卫华的想法):问能否把GNF中A®a中的a用作00思考:崔同学实际是想设计接受{1nam1n

42、n,m≥1}的PDA以简化,但又没有底气这种想法很大胆(褒义的"

43、大胆")也是可行的.过程是:先设计PDA接受L={1nam1n

44、n,m≥1}这儿å={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的状态q2δ

45、2(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状态下读完所有的符号,且栈中只余Z0δ2(q4,ε,Z0)={(q5,ε)}综上,设计的PDA为:M2=(

46、{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

47、状态下读入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,

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。