Qt 5开发及实例（第4版）CHAP2new

2.1略。2.2a.利用语言A={ambncn|m,n(0}和A={anbncm|m,n(0}以及例3.20，证明上下文无关语言在交的运算下不封闭。b.利用(a)和DeMorgan律(定理1.10)，证明上下文无关语言在补运算下不封闭。证明：a.先说明A,B均为上下文无关文法，对A构造CFGC1S(aS|T|(T(bTc|(对B,构造CFGC2S(Sc|R|(R(aRb由此知A,B均为上下文无关语言。但是由例3.20,A∩B={anbncn|n(0}不是上下文无关语言，所以上下文无关语言在交的运算下不封闭。b.用反证法。假设CFL在补运算下封闭，则对于(a)中上下文无关语言A,B，,也为CFL，且CFL对并运算封闭，所以也为CFL，进而知道为CFL，由DeMorgan定律＝A∩B，由此A∩B是CFL,这与(a)的结论矛盾，所以CFL对补运算不封闭。2.3略。2.4和2.5给出产生下述语言的上下文无关文法和PDA，其中字母(={0,1}。a.{w|w至少含有3个1}S→A1A1A1AA→0A|1A|(b.{w|w以相同的符号开始和结束}S→0A0|1A1A→0A|1A|(c.{w|w的长度为奇数}S→0A|1AA→0B|1B|(B→0A|1Ad.{w|w的长度为奇数且正中间的符号为0}S→0S0|1S1|0S1|1S0|0e.{w|w中1比0多}S→A1AA→0A1|1A0|1A|AA|(f.{w|w=wR}S→0S0|1S1|1|0g.空集S→S2.6给出产生下述语言的上下文无关文法：a．字母表{a,b}上a的个数是b的个数的两倍的所有字符串组成的集合。S→bSaSaS|aSbSaS|aSaSbS|(b．语言{anbn|n(0}的补集。见问3.25中的CFG:S→aSb|bY|TaT→aT|bT|(c．{w#x|w,x({0,1}*且wR是x的子串}。S→UVU→0U0|1U1|WW→W1|W0|#V→0V|1V|(d．{x1#x2#(#xk|k(1,每一个xi({a,b}*,且存在i和j使得xi＝xjR}。S→UVWU→A|(A→aA|bA|#A|#V→aVa|bVb|#B|#B→aB|bB|#B|#W→B|(2.8证明上下文无关语言类在并,连接和星号三种正则运算下封闭。a.A(B一：CFG。设有CFGG1＝(Q1,(,R1,S1)和G2=(Q2,(,R2,S2)且L(G1)=A,L(G2)=B。构造CFGG=(Q,(,R,S0)，其中Q=Q1(Q2({S0},S0是起始变元，R=R1(R2({S0(S1|S2}.方法二：PDA。设P1=(Q1,(,(1,(1,q1,F1)识别A，P2=(Q1,(,(2,(2,q2,F2)是识别B。则如下构造的P=(Q,(,(,(,q0,F)识别A(B，其中1)Q=Q1(Q2({q0}是状态集，2)(＝(1((2，是栈字母表，3)q0是起始状态，4)F＝F1(F2是接受状态集，5)(是转移函数，满足对任意q(Q,a(((,b(((((q,a,b)=b.连接AB方法一：CFG。设有CFGG1＝(Q1,(,R1,S1)和G2=(Q2,(,R2,S2)且L(G1)=A,L(G2)=B。构造CFGG=(Q,(,R,S0)，其中Q=Q1(Q2({S0},S0是起始变元，R=R1(R2({S0(S1S2}.方法二：PDA。设P1=(Q1,(,(1,(1,q1,F1)识别A，P2=(Q1,(,(2,(2,q2,F2)是识别B，而且P1满足在接受之前排空栈(即若进入接受状态，则栈中为空)这个要求。则如下构造的P=(Q,(,(,(,q1,F)识别A(B，其中1)Q=Q1(Q2是状态集，2)(＝(1((2，是栈字母表，3)q1是起始状态，4)F＝F1(F2是接受状态集，5)(是转移函数，满足对任意q(Q,a(((,b(((((q,a,b)=c.A*方法一：CFG。设有CFGG1＝(Q1,(,R1,S1)，L(G1)=A。构造CFGG=(Q,(,R,S0)，其中Q=Q1({S0},S0是起始变元，R=R1({S0(S0S0|S1|(}.方法二：PDA。设P1=(Q1,(,(1,(1,q1,F1)识别A，而且P1满足在接受之前排空栈(即若进入接受状态，则栈中为空)这个要求。则如下构造的P=(Q,(,(,(,q1,F)识别A*，其中1)Q=Q1({q0}是状态集，2)(＝(1，是栈字母表，3)q0是起始状态，4)F＝F1({q0}是接受状态集，5)(是转移函数，满足对任意q(Q,a(((,b(((((q,a,b)=2.9证明在3.1节开始部分给出的文法G2中，字符串thegirltouchestheboywiththeflower有两个不同的最左派生，叙述这句话的两个不同意思。<句子>(<名词短语><动词短语>(<复合名词><动词短语>(<冠词><名词><动词短语>(a_<名词><动词短语>(a_girl_<动词短语>(a_girl_<复合名词>(a_girl_<动词>< 名词短语>(a_girl_touches_< 名词短语>(a_girl_touches_<复合名词><介词短语>(a_girl_touches_<冠词><名词><介词短语>(a_girl_touches_the_<介词><复合名词>(a_girl_touches_the_boy_<介词短语>(a_girl_touches_the_boy_<介词><复合名词>(a_girl_touches_the_boy_with_<复合名词>(a_girl_touches_the_boy_with_<冠词><名词>(a_girl_touches_the_boy_with_the_<名词>(a_girl_touches_the_boy_with_the_flower含义是：女孩碰这个带着花的男孩<句子>(<名词短语><动词短语>(<复合名词><动词短语>(<冠词><名词><动词短语>(a_<名词><动词短语>(a_girl_<动词短语>(a_girl_<复合动词><介词短语>(a_girl_<动词>< 名词短语><介词短语>(a_girl_touches_< 名词短语><介词短语>(a_girl_touches_<冠词><名词><介词短语>(a_girl_touches_the_< 名词><介词短语>(a_girl_touches_the_boy_<介词短语>(a_girl_touches_the_boy_<介词><复合名词>(a_girl_touches_the_boy_with_<复合名词>(a_girl_touches_the_boy_with_<冠词><名词>(a_girl_touches_the_boy_with_the_<名词>(a_girl_touches_the_boy_with_the_flower含义是：女孩用花碰这个男孩2.10给出产生语言A={aibjck|i,j,k(0且或者i=j或者j=k}的上下文无关文法。你给出的文法是歧义的吗？为什么？解：下面是产生A的一个CFG:S(UV|ABU(aUb|(V(cV|(A(aA|(B(bUc|(这个CFG是歧义的，因为字符串abc有如下两种不同的最左派生：S(UV(aUbV(abV(abcV(abcS(AB(aAV(aV(abVc(abc2.11给出识别2.10中语言A的下推自动机的非形式描述。解：其非形式描述为：此PDA有两个非确定性的分支：一个分支先读a，并且每读一个a将一个a推入栈中，当碰到b时，每读一个b从栈中弹出一个a，若没有a可弹出则拒绝，最后读c且不改变栈中的内容，若此时栈为空则接受。另一个分支也是先读a，但不改变栈中内容，当碰到b时，每读一个b将一个b推入栈中，再读c,每读一个c从栈中弹出一个b，若没有a可弹出则拒绝，若c读完后栈为空则接受。开始时，读输入串的字符，非确定性的选择一个分支运行，若有一个分支接受则接受，否则拒绝。2.14设有上下文无关文法G:S(TT|UU(0U00|#T(0T|T0|#a.用普通的语言描述L(G)。b.证明L(G)不是正则的。解：a.A={0i#0j#0k|i,j,k(0}({0i#02i|i(0}。b.取s=0p#02p,则对于任意划分s=xyz(|xy|(p,|y|>0),xynz=0p+i#02p(A,所以不是正则的。2.15用定理2.6中给出的过程，把下述CFG转换成等价的乔姆斯基范式文法。A(BAB|B|(B(00|(解：添加新起始变元S0,去掉B((S0(AS0(AA(BAB|B|(A(BAB|AB|BA|B|(B(00|(B(00去掉A((,去掉A(BS0(AS0(AA(BAB|AB|BA|B|BBA(BAB|AB|BA|00|BBB(00B(00去掉S0(A,添加新变元S0(BAB|AB|BA|00|BBS0(VB|AB|BA|UU|BBA(BAB|AB|BA|00|BBA(VB|AB|BA|UU|BBB(00B(UUV(BAU(02.x先说明如何把正则表达式直接转换成等价得上下文无关文法，然后利用问题xxx的结果，给出每一个正则语言都是上下文无关文法的一个证明。解：设有正则表达式T，将其转化为上下文无关文法。1)首先添加S(T，且令S为起始变元。2)根据T的不同形式，按如下方式添加规则1．若T＝a((，则在规则集中添加T(a,2．若T＝(，则在规则集中添加T((,3．若T＝(，则在规则集中添加T(T，4．若T＝A(B，则在规则集中添加T(A|B，5．若T＝A·B,则在规则集中添加T(AB，6．若T＝A*,则在规则集中添加T(A,和A(AA|(3)若有新添加的变元，则根据其所对应的表达式转第2步，直到没有新的变元出现。下面来证明每一个正则语言都是上下文无关的由正则语言与正则表达式的等价性可知：对于一个正则语言都存在一个描述他的正则表达式，由前述讨论可知，这个正则表达式可转换为一个与之等价的上下文无关的文法。因此，此正则语言能由这个上下文无关文法产生。所以正则语言是上下文无关的。2.18a.设C是上下文无关语言，R是正则语言。证明语言C(R是上下文无关的。b．利用a证明语言A={w|w({a,b,c}*,且含有数目相同的a,b,c}证明：a.设P=(Q1,(,(,(1,q1,F1)是一个识别C的PDA，N=(Q2,(,(2,q2,F2)是识别R的一台NFA。下面构造识别C(R的PDA如下S=(Q,(,(,(,q0,F):1)Q=Q1×Q2,是状态集，2)q0=(q1,q2)是起始状态，3)F=F1×F2,是接受状态集，4)(是转移函数，满足对任意q(Q1,r(Q2,a(((,b(((,(((q,r),a,b)={((q’,r’),c)|q’((1(q,a),(r’,c)((2(r,a,b)}.b.A(a*b*c*={anbncn|n(0},若A是上下文无关的，则由a中命题知{anbncn|n(0}也是上下文无关的，矛盾。2.26证明：设G是一个Chomsky范式CFG，则对任一长度(2的字符串w(L(G),w的任何派生恰好有2n－1步。证明：(用数学归纳法)当n=2时，对于Chomsky范式CFG，长度为2的字符串必由3步派生，此时命题为真。假设当2(n(k时命题为真。当n=k+1时，对于长度为k+1的字符串s=s1s2(sk+1，存在S0的一个直接派生S0(AB，使得A产生子串s1s2(sp，B产生子串sp+1sp+2(sk+1，其中1(p(k+1。由归纳假设，A产生子串s1s2(sp需要2p-1步派生，而B产生子串sp+1sp+2(sk+1需要2(k+1-p)-1步派生。因此，S0产生字符串s共需2(k+1)-1步派生。即当n=k+1时命题亦真。因此，由G产生长度为n(2的字符串需要2n-1派生。2.30用泵引理证明下述语言不是上下文无关的：a.{0n1n0n1n|n(0}假设语言上下文无关，设p为泵长度，取S=0p1p0p1p.由泵引理知，S可以划分为uvxyz且满足泵引理条件。考察子串vxy,首先，它一定横跨S的中点，否则，若vxy位于S的前半段，由于|vxy|(p,则uv2xy2z中1将是后半段字符串的第一个字符，即不可能是0n1n0n1n的形式。同理，vxy也不可能位于S后半段的位置上。但是,若vxy跨越S的中点时，将S抽取成uxz，它形如0p1i0j1p,i，j不可能都为p，即uxz不可能是0n1n0n1n的形式。综上，可知S不能被抽取，因此，该语言不是上下文无关的。b.{0n#02n#03n|n(0}假设语言上下文无关，设p为泵长度，取S=0p#02p#03p,由泵引理知，S可以划分为uvxyz且满足泵引理条件。考察子串vxy。首先，v,y中不能有#，否则S抽取成uxz后，其中#个数(1。由条件3，vxy或者位于第2个#之前，或者位于第1个#之后。下面讨论这两种情况：1．此时，uv2xy2z中第3部分0的个数保持不变，而前面部分的0的个数至少有一个增加，因此，uv2xy2z不在该语言中。2．此时，uv2xy2z中第1部分0的个数保持不变，而第2，3部分0的个数至少有一个增加，也有uv2xy2z不在该语言中。因此，该语言不是上下文无关的。c.{w#x|w,x({a,b}*,w是x的子串}假设该语言上下文无关，设p为泵长度，取S=0p1p#0p1p,由泵引理知，S可以划分为uvxyz且满足泵引理条件。显然，v,y中不包含#，不然抽取后的S=uxz中将不含#从而不在该语言中。子串vxy不能落在#的左侧，否则uv2xy2z中#左侧的字符串长度将大于右边。子串vxy不能落在#的右侧，否则uxz中#左侧的字符串长度也会大于右边。现在假设#(x，则必存在不全为0的i,j，使得vy=1i0j，下面分两种情况考虑：1．j(0,则uxz=0p1p-i#0p-j1p不在该语言中2．j=0,则uv2xy2z中#左侧的字符串长度大于右边，不在该语言中。因此，该语言不是上下文无关的。d.{x1#x2#(#xk|k(2,每一个xi({a,b}*,且存在xi＝xj}假设该语言上下文无关，设p为泵长度，取S=apbp#apbp,由泵引理知，S可以划分为uvxyz且满足泵引理条件。显然，v,y中不包含#，不然抽取后的S=uxz中将不含#从而不在该语言中。子串vxy不能落在#的左侧，否则uv2xy2z中#左侧的字符串长度将大于右边。子串vxy不能落在#的右侧，否则uxz中#左侧的字符串长度也会大于右边。于是vxy跨越#两侧.此时，S经抽取成uxz后，具有apbi#ajbp的形式，其中，i,j不全为p。因此，uxz不在该语言中。综上该语言不是上下文无关的。2.34考虑语言B=L(G),其中G是练习3.13中给出的文法。定理3.19关于上下文无关语的泵引理称存在关于B的泵长度p。p的最小值等于多少？要求给出证明。证明：p的最小值为4。令D={0i#0j#0k|i,j,k(0},E={0i#02i|i(0},则L(G)=D(E。L(G)中长度为1的字符串仅有#,不能被抽取。L(G)中长度为2的字符串仅有#,也不能被抽取。D中长度(3的字符串必含有0，所以一定可以被抽取。E中长度(3的字符串也可以被抽取(E中没有长度等于3的字符串)。只需令uvxyz分别为v=0,x=#,y=00,u,z为两边其余的字符串即可。注意到此时|vxy|＝4。但是泵长度不能等于3。因为若p=3，则要求|vxy|(3，但是对于E中的字符串来说，每在#左边抽取1个0，则同时必须在#右边抽取2个0，即|vy|(3，又x必须包含#,所以任何有效的抽取必有|vxy|(4。综上所述，p的最小值为4。2.35设G是一个含有b个变元的乔姆斯基范式CFG。证明：如果G产生某个字符串使用了至少2b步的派生，则L(G)是无穷的。证明：设G产生字符串S需要至少2b步。由于一个分支点(变元)对应一次派生，所以S的语法树τ至少有2b个分支点。又由于在乔姆斯基范式下，一个分支点至多有两个子分支点(这意味着层数(n的结点个数(2b－1)，从而τ的由分支点组成的子树的高度大于等于b+1。τ有一条路径上分支点(变元)个数(b+1。由鸽巢原理：必有某个变元R在该路径上出现至少两次。不妨假设R出现在路径上最下面的b+1个变元中。按上图所示，将S划分为uvxyz，在每一个R的下面有一棵子树，它产生S的一部分。上面的R有一棵较大的子树，产生vxy，下面的R有一棵较大的子树，产生x，由于这两棵子树由同一个变元产生，因而可以相互替换。这里采用如下操作：反复用较大子树去替换较小子树，则我们得到对于任意n>1,uvnxynz(L(G)。所以若我们能证明v,y不全为ε，则L(G)是无穷的。事实上，由乔姆斯基范式的特点，上面一个R的派生选择的必为R(AB形式的规则，而且不可能有A(和B(，所以v,y不全为(。从而命题得证。2.26给出一个语言，它不是上下文无关的、但满足泵引理的三个条件。要求给出证明。解：令A＝{aibjckdl|i,j,k,l(0,且当i=1时，j=k=l}，则：(1)A满足泵引理的三个条件。取泵长度p＝1。对A中任意长度大于1的字符串s=aibjckdl，分情况可以如下抽取：若i=1,则j=k=l,取v=a,uxy=(，z=bjcjdj,则对(n(0，uvnxynz=aibjcjdj(A；若i(2，且j,k,l不同时为0，不妨设j(0，取u=ai,v=b,xy=(，z=bj-1ckdl,则对(n(0，uvnxynz=aibj-1+nckdl(A；若i(2，且j=k=l=0,取u=ai-1,v=a,xyz=(,则对(n(0，uvnxynz=ai-1+n(A；若i=0，则j,k,l不同时为0，不妨设j(0，取v=b,uxy=(，z=bj-1ckdl,则对(n(0，uvnxynz=bj-1+nckdl(A。(2)A不是上下文无关语言。事实上，若A为上下文无关语言，另取正则语言R=ab*c*d*，由问题3.17可知，L(R是上下文无关的。但这与L(R={abncndn|n(0}不是一个上下文无关语言矛盾。因此，A不是上下文无关的。zyxvuRRT(,1(((,1((0,(((1,((1(,1((0,0((1,1((0,((00,(((1,(((1,((10,(((1,(((0,(((1,((((,$(((,(($0,0((1,0((0,((00,(((1,((00,1((1,0(((,$(((,(($(,1((0,((0(,1((1,((1(,(((1,((((,$(((,(($0,0((1,1((0,((00,(((1,((1_1098900499.unknown_1099051639.unknown_1099053113.unknown_1099053382.unknown_1098900521.unknown_1098990875.unknown_1098900405.unknown_1098900447.unknown_1098900345.unknown