第6789章-作业及参考答案

资源描述

《第6789章-作业及参考答案》由会员分享，可在线阅读，更多相关《第6789章-作业及参考答案（12页珍藏版）》请在金锄头文库上搜索。

1、第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|

2、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的

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(M

4、1)=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为

5、开始状态，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状态下读

6、完所有的符号，且栈中只余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

7、)=(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, )综上，设计的PD

8、A为：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)匹配阶段的工作, 再匹配的

9、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,

10、 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之四

11、 (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(q

12、2, 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

展开阅读全文