第6789章 作业及参考答案.doc

第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|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的构造方法，设计出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(M1)=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为开始状态，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状态下读完所有的符号，且栈中只余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)=(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, )综上，设计的PDA为：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)匹配阶段的工作, 再匹配的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, 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之四 (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(q2, 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), (q, A), (q, ) (q, b, A)=(q, BA),(q, ) 从而N(M)=L(G) -一定要点出接受方式是以空栈方式接受主要问题(1)不按定理的方法构造:PDA M= (p, q,a,b,S,A,B , , q, S, )!学会机械化的构造方法如果另起炉灶(鼓励这样做, 唯有此才能前进, 才能进步, 这也是终极目标), 但要先有前期工作.不能突然而至, 似有照猫画虎嫌疑, 结果不猫不虎. (2) 按教材上的原题做: SaBB|bAA, BaBB|aA|a, AbBA|有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), (q, A), (q, ) (q, b, A)=(q, BA) (q, , A)=(q, ) 从而N(M)=L(G)错误！原因: 给出的CFG是GNF吗? 这能保证这一点, 不能这么做.按原题的正确做法是:首先, L(G)消除文法SaBB|bAA, BaBB|aA|a, AbBA|中的空产生式, 并转换为等价的GNF, 有SaBB|bAA|bA|b, BaBB|aA|a, AbBA|bB从而有PDA M= (q,a,b,S,A,B , , q, S, ) (q, a, S)=(q, BB) (q, b, S)=(q, AA), (q, A), (q, ) (q, a, B)=(q, BB), (q, A), (q, ) (q, b, A)=(q, BA), (q, B)从而N(M)=L(G)11、构造CFG，产生如下PDA用空栈接受的语言(1)M=(q,p,0,1,A,B,C, , q, A, )(q, 0, A)=(q, B), (q, BB)(q, 1, A)=(q, C), (q, CC)(q, 0, B)=(q, BB), (q, BBB), (p, )(q, 1, B)=(q, CB), (q, CCB)(q, 0, C)=(q, BC), (q, BBC)(q, 1, C)=(q, CC), (q, CCC), (p, )(p, 0, B)=(p, )(p, 1, C)=(p, )解：(根据定理7-4证明中提供的构造方法完成)构造得CFG G=(V, 0,1, P, S), 其中V=SpAp,pBp,pCp,pAq,pBq,pCq,qAp,qBp,qCp,qAq,qBq,qCq产生式集合P由以下产生式构成(约定符号pa,pb,pcq,p)：首先有：SqAp| qAq由(q, B) (q, 0, A)有qApa 0qBpa, 因pa q,p, 展开有：qAp 0qBp和qAq 0qBq由(q, BB) (q, 0, A)有qApb 0qBpapaBpb因pa,pb q,p，展开有：qAp 0qBppBp, qAq 0qBppBq, qAp 0qBqqBp, qAq 0qBqqBq因pa q,p展开有qAp 0qBp和qAq 0qBq由(q, C) (q, 1, A) 有qApa 1qCpa, .(以下同法展开)由(q, CC) (q, 1, A) 有qApb 0qCpa paCpb由(q, BB) (q, 0, B) 有qBpb 0qBpa paBpb由(q, BBB) (q, 0, B) 有qBpc 0qBpa paBpb pbBpc由(p, ) (q, 0, B) 有qBp 0由(q, CB) (q, 1, B) 有qBpb 1qCpa paBpb由(q, CCB) (q, 1, B) 有qBpc 1qCpa paCpb pbBpc由(q, BC) (q, 0, C) 有qCpb 0qBpa paCpb由(q, BBC) (q, 0, C) 有qCpc 0qBpa paBpb pbCpc由(q, CC) (q, 1, C) 有qCpb 1qCpa paCpb由(q, CCC) (q, 1, C) 有qCpc 1qCpa paCpb pbCpc由(p, ) (q, 1, C) 有qCp 1由(p, ) (p, 0, B) 有pBp 0由(p, ) (p, 1, C) 有pCp 1可以对上面的CFG进行化简。主要问题: (1)有些同学看不懂问题: 要构造的是CFG (2)要把五元组首先写出来 (3)我意想不到的错误 根据给定PDA, 设计出相应的GNF: A0B|0BB|1C|1CC B0BB|0BBB|0|1CB|1CCB C0BC|0BBC|1CC|1CCC|1(有些还在继续) 则相应的CFG是: A0B|1C B0B|BB|1C|0 CCB|1C| 0BC|CC|1(或者有些在这样继续, 可能是在做补充题) 构造与其等价的以终止状态接受的PDA是M=( , , , , , , )甚至M=( , , , , , , )补充题：构造与11(1)中PDA等价的以终止状态接受语言的PDA M11(1)M=(q,p,0,1,A,B,C, , q, A, )(q, 0, A)=(q, B), (q, BB)(q, 1, A)=(q, C), (q, CC)(q, 0, B)=(q, BB), (q, BBB), (p, )(q, 1, B)=(q, CB), (q, CCB)(q, 0, C)=(q, BC), (q, BBC)(q, 1, C)=(q, CC), (q, CCC), (p, )(p, 0, B)=(p, )(p, 1, C)=(p, )解：(根据定理7-4证明中提供的构造方法完成) PDA M= (q,p,0,1,A,B,C, q, A, )取PDA M = ( q,p, q02，qf，0,1， A,B,C,Z02，q02，Z02，qf)的定义如下，M进入M的开始状态：(q02，Z02)=(q，AZ02)M2完全模拟M1的移动：对于(q, a, Z)q,p0,1, A,B,C,(q, a, Z)= (q, a, Z)，即有 (q, 0, A)=(q, 0, A)=(q, B), (q, BB) (q, 1, A)=(q, 1, A)=(q, C), (q, CC) (q, 0, B)=(q, 0, B)=(q, BB), (q, BBB), (p, ) (q, 1, B)=(q, 1, B)=(q, CB), (q, CCB) (q, 0, C)=(q, 0, C)=(q, BC), (q, BBC) (q, 1, C)=(q, 1, C)=(q, CC), (q, CCC), (p, ) (p, 0, B)=(p, 0, B)=(p, ) (p, 1, C)=(p, 1, C)=(p, ) M的栈已空时，Z02成为栈中唯一符号，M进入终止状态，以终态接受, 有(q, ,Z02)= (qf, )和(p, ,Z02)= (qf, ) 则L(M) = L(M)存在的问题:(1)不写解题说明;(2) PDA M = (, , , , , , )6、构造PDA M, 使L(M)=N(M)=1n0n|n11n02n|n1解: (1)首先构造PDA M1, 使L(M1)=N(M1)=1n0n|n1, 有 M1=(q1, q1f,0,1,A, Z1,1, q1, Z1, q1f) 其中1定义为: 1 (q1, 1, Z1)=( q1, AZ1) 1 (q1, 1, A)=( q1, AA) 1 (q1, 0, A)=( q1, ) 1 (q1, , Z1)=( q1f, ) (2)再构造PDA M2, 使L(M2)=N(M2)=1n02n|n1, 有 M2=(q2, q2f,0,1,B,Z2,2, q2, Z2, q2f) 其中2定义为: 2 (q2, 1, Z2)=( q2, BBZ2) 2 (q2, 1, B)=( q2, BBB) 2 (q2, 0, B)=( q2, ) 2 (q2, , Z2)=( q2f, ) (3)在M1和M2基础上构造PDA M, 使L(M)=N(M)=1n0n|n11n02n|n1M=( q0, qf,q1, q1f, q2, q2f ,0,1,A,B,Z1,Z2, Z0 , q0, Z0, qf)其中定义为:在M开始工作时, 转入M1开始工作, 栈底保留(q, , Z0)=( q1, Z1Z0) M完全模拟M1的工作对(q, a, Z)q1, q1f0,1, A, Z1, (q, a, Z)= 1 (q, a, Z)在M1本身的栈空且进入终止状态后, 进入M2工作, 栈底仍然保留(q1f, , Z0)=( q2, Z2Z0) M完全模拟M2的工作对(q, a, Z)q2, q2f0,1, B, Z2, (q, a, Z)= 2 (q, a, Z)在M2本身的栈空且进入终止状态后, 进入M的终止状态且清空栈(q2f, , Z0)=( qf, ) 这样, L(M)=N(M)=1n0n|n11n02n|n1若仅构造以空栈方式接受的PDA，可用解法2（根据2006级岳光同的思路整理）产生1n0n|n1的文法是：S11S1A|1A, A0产生1n02n|n1的文法是：S21S2BB|1BB, B0设计PDA M1 = (q1 ,0,1,S1A ,1, q1, S1, )1(q1,1,S1)=( q1, S1A), ( q1, A)1(q1,0,A)=( q1, )有：N(M1) = 1n0n|n1设计 PDA M2 = (q2 ,0,1,S2, A,2, q2, S2, )2(q2,1,S2)=( q2, S2BB), ( q2, BB)2(q2,0,B)=( q2, )有：N(M2) = 1n02n|n1增加一个开始状态q0，增加一个初始栈符号S，开始时使M1工作，同时在栈中置入M2的栈底符号，当M1的栈空后，进入M2工作，构造的PDA M是：M= (q0, q1, q2 ,0,1, S, S1, S2, A, B, q0, S, )(q0, ,S)=( q1, S1S2)(q1,1,S1)=( q1, S1A), ( q1, A)(q1,0,A)=( q1, )(q1, ,S2)=( q2, S2)(q2,1,S2)=( q2, S2BB), ( q2, BB)(q2,0,B)=( q2, )有N(M) = 1n0n|n11n02n|n1补充题：构造产生(识别) 语言L的CFGL=0n1n0m12m|n,m1解: L(G) =0n1n0m12m|n,m1=0n1n|n10n12n|n1 构造G1=(A,0,1, A01|0A1,A), L(G1)= 0n1n|n1构造G2=(B,0,1, B011|0B11,A), L(G2)= 0n12n|n1在G1和G2基础上可以构造出G=(S,A,B,0,1, SAB, A01|0A1,B011|0B11, S),L(G)= L(G1) L(G2)推荐: 对两个补充题, 要有利用运算性质构造的意识第9章 P3183、给出M处理4+3的过程解：输入4+3表示为00001000, 则有q0000010000q2000100000q2001000000q2010000000q2100000000q2000000000q2000000000q2000000000q2B0000000q30B00000000q1B5、设计识别下列语言的图灵机(1) 1n0m |n m1解法1：设q0为初始状态，读到1时将其置为X，向后查找对应的0，找到后标记为Y，再向前查找未匹配的1，直到全部的0变为Y后，在之前仍有1或1正好全被标注为X，这时进入终止状态。X.X1.1YY00Bq01/XY/Yq11/1Y/Yq2Y/Y1/10/YB/Bq3Y/Yq4B/BX/X 构造思路如下：TM M=(q0,q1,q2,q3,q4,0,1,0,1,X,Y,B, q0,B,q4)(q0,1)=(q1,X,R)(q1,1)=(q1,1,R)(q1,Y)=(q1,Y,R)(q1,0)=(q2,Y,L)(q2,Y)=(q2,Y,L)(q2,1)=(q2,1,L)(q2,X)=(q0,X,R)(q0,Y)=(q3,Y,R)(q3,Y)=(q3,Y,R)(q3,B)=(q4,B,R)(q1,B)=(q4,B,R)接受11100的过程：解法2：(采用多道技术解决)设TM M有两个道，第二道放要识别的串，第一道初始全为B，用V标记已匹配的符号