资源描述：
《第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,
