计算理论习题答案

2.2 a.利用语言 A=ambncn | m,n 0和 A=anbncm | m,n 0以及例，证明上下文无关语言在交的运算下不封闭。b.利用(a)和DeMorgan律(定理，证明上下文无关语言在补运算下不 封闭。证明：a.先说明A,B均为上下文无关文法，对 A构造CFG CS aS|T|T bTc|对B,构造CFG CS Sc|R|R aRb由此知A,B均为上下文无关语言。但是由例，A A B=anbncn|n 0不是上下文无关语言，所以上下文无关语言在交的运算下不封闭。b.用反证法。假设CFL在补运算下封闭，则对于(a)中上下文无关语言A,B, A, B也为CFL且CFLM并运算封闭，所以A B也为CFL进而知道A B 为CFL由DeMorgan定律A B =AA B,由此AH B是CFL,这与(a)的结论矛 盾，所以CFLM补运算不封闭。和 给出产生下述语言的上下文无关文法和 PDA其中字母表 =0,1。a. w | w至少含有3个15- A1A1A1AZ 0A|1A|b. w | w以相同的符号开始和结束S- 0A0|1A1Z 0A|1A|c. w | w的长度为奇数S- 0A|1AZ 0B|1B|A 0A|1A0101d. w | w的长度为奇数且正中间的符号为 0S- 0S0|1S1|0S1|1S0|0e. w | w中1比0多S- A1A2 0A1|1A0|1A|AA|f. w | w=w RS- 0S0|1S1|1|0给出产生下述语言的上下文无关文法：a.字母表a,b上a的个数是b的个数的两倍的所有字符串组成的集 合。S -bSaSaS|aSbSaS|aSaSbS|b.语言anbn|n0的补集。见问题中的CFG:Sf aSb|bY|TaTf aT|bT|c. w#x | w, x 0,1且 WR是 x 的子用。S一 UVU 0U0|1U1|WW W1|W0|#V- 0V|1V|d.仅檄力#Xk|k1,每一个Xi a,b * ,且存在i和j使得Xi=XjR。SfUVWU A|Af aA|bA|#A|#Vf aVa|bVb|#B|#Bf aB|bB|#B|#W B|证明上下文无关语言类在并，连接和星号三种正则运算下封闭。a. A B方法一：CFG设有 CF3=(Qi,Ri,Si)和 G=(Q, 尺冬)且 L(Gi)=A,L(G2)=B。构造 CFG G=(Q, RS0),其中Q= Q Q So, S 0是起始变元，R= R R So Si|Sz.方法二：PDA设 Pi=(Qi,1,1,q1,F1)识别 A,P2=(Qi, , 2, 2,q2,F2)是识别 B。则如下构造的P=(Q, , ,q0,F)识别A B,其中1) Q=Q Q q。是状态集，2) =i 2,是栈字母表，3) q。是起始状态，4) F= Fi F2是接受状态集，5) 是转移函数，满足对任意q Q, a ,b(qi, ), (q2, ),若qq,a b(q,a,b尸i(q,a,b),若q Qi,b ( i)2(q,a,b),若q Q2,b ( 2),else.b.连接AB方法一：CFG设有 CFGG=(Qi, ,Ri,Si)和 G=(Q, 尺52)且 L(Gi)=A, L(Gz)=B。构造 CFG G=(Q, RS0),其中Q= Q Q So, S 0是起始变元，R= R R So S1S2.方法二：PDA设 Pi=(Qi,1,1,q1,F1)识别 A,P2=(Qi,2,2,q2,F2)是识别 B,而且Pi满足在接受之前排空栈(即若进入接受状态，则栈中为空)这个要求。则如下构造的P=(Q, , ,q 1,F)识别A B,其中1) Q=Q Q是状态集，2) =12,是栈字母表,3) 5是起始状态，4) F= F1 F2是接受状态集，若 q Q1 F1,b ( 1)若 q F1,a b ,若q F1,(a,b)(,),若q Q2,b ( 2),else.5) 是转移函数，满足对任意q Q, a ,b1(q,a,b), 1(q,a,b) (q2, ), (q,a,b)=1(q,a,b),2(q,a,b),J c. A方法一：CFG 设有 CFG G=Q, RS), L(G)=A。构造 CFG G=(Q, ,R,S。)，其中 Q=Q S0, So 是起始变元，R=R S0 &$| .方法二：PDA设Pi=(Qi, i, i,q i,Fi)识别A,而且Pi满足在接受之前排空栈(即若进入接受状态，则栈中为空)这个要求。 - . . . . * .则如下构造的P=(Q, , ,qi,F)识别A,其中1) Q=Q q。是状态集，2) =i,是栈字母表,3)4) F= Fi5) 是转移函数,(q,a,b)=q。是起始状态,q。是接受状态集满足对任意q Q, ai(q, a, b),i(q,a,b) (qi, ),i(q, a, b),(qi,),b若 q QiFi,若 q Fi,a b,若q Fi,(a,b)(,)若 q qo,a b,else证明在节开始部分给出的文法 G中，字符串the girl touches the boy with the flower有两个不同的最左派生，叙述这句话的两个不同意思。旬子名词短语 动词短语复合名词 动词短语冠词 备词 对词短语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_v 名词 a girl touches the boy w让h the v 名词 a girl touches the boy w让h the flower含义是：女孩碰这个带着花的男孩v句子v名词短语 V复合名词 V冠词 寻词 对词短语 a_v名词司词短语 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_v 名词 a girl touches the boy w让h the v 名词a_girl_touches_the_boy_with_the_flower含义是：女孩用花碰这个男孩给出产生语言A=aibjck| i,j,k 0且或者i=j或者j=k的上下文无关文 法。你给出的文法是歧义的吗为什么解：下面是产生A的一个CFG:S UV|ABU aUb|V cV|A aA|B bUc|这个CF班歧义的，因为字符串abc有如下两种不同的最左派生：S UV aUbV abV abcV abcS AB aAV aV abVc abc给出识别中语言A的下推自动机的非形式描述。解：其非形式描述为：此PDAt两个非确定性的分支：一个分支先读 a,并且每读一个a将一个 a推入栈中，当碰到b时，每读一个b从栈中弹出一个a,若没有a可弹出则 拒绝，最后读c且不改变栈中的内容，若此时栈为空则接受。另一个分支也是 先读a,但不改变栈中内容，当碰到b时，每读一个b将一个b推入栈中，再 读c,每读一个c从栈中弹出一个b,若没有a可弹出则拒绝，若c读完后栈 为空则接受。开始时，读输入用的字符，非确定性的选择一个分支运行，若有 一个分支接受则接受，否则拒绝。设有上下文无关文法G:S TT|UU 0U00|#a.用普通的语言描述L(G)。b.证明L(G)不是正则的。解： a. A=0 i#O#0k | i, j, k 0 0 i#02i | i 0。b.取 s=0P#0:则对于任意划分s=xyz(|xy| p, |y|0),xynz=o#02p A,所以不是正则的。用定理中给出的过程，把下述CFG专换成等价的乔姆斯基范式文法。A BAB|B|B 00|解：添加新起始变元So,So AA BAB|B|B 00|去掉BSo AA BAB|AB|BA|B|B 00去掉A ,So AA BAB|AB|BA|B|BBB 00去掉A BSo AA BAB|AB|BA|00|BBB 00去掉So A,So BAB|AB|BA|00|BBA BAB|AB|BA|00|BBB 00添加新变元So VB|AB|BA|UU|BBA VB|AB|BA|UU|BBB UUV BA先说明如何把正则表达式直接转换成等价得上下文无关文法，然后利用问题xxx的结果，给出每一个正则语言都是上下文无关文法的一个证明 解：设有正则表达式T,将其转化为上下文无关文法。1)首先添加S T,且令S为起始变元2)根据T的不同形式，按如下方式添加规则 . 若T=a .若T=, .若T=, . 若T= A B, . 若 T= A- B, . 若T= A*,则在规则集中添加 则在规则集中添加 则在规则集中添加 则在规则集中添加 则在规则集中添加 则在规则集中添加T a,T ,T T,T A|B,T AB,T A,和 A AA|3)若有新添加的变元，则根据其所对应的表达式转第2步，直到没有新的变元出现下面来证明每一个正则语言都是上下文无关的由正则语言与正则表达式的等价性可知：对于一个正则语言都存在一 个描述他的正则表达式，由前述讨论可知，这个正则表达式可转换为一个与之 等价的上下文无关的文法。因此，此正则语言能由这个上下文无关文法产生。 所以正则语言是上下文无关的。2.18 a.设C是上下文无关语言，R是正则语言。证明语言 C R是上下 文无关的。b.利用a证明语言A=w | w a,b,c *,且含有数目相同的a,b,c证明：a.设 P=(Q, i,qi,Fi)是一个识别 C的 PDA,N=(Q,2,q2,F2)是识别R的一台NFA下面构造识别 C R的PDA如下S二(Q, , , ,q0,F):1) Q=QX Q2,是状态集，2) qo=(qi,q 2)是起始状态,3) F= F1XF2,是接受状态集，4) 是转移函数，满足对任意 q Q,rQ2,a,b ,(q,r),a,b尸(q ,r ),c) | q i(q,a),(r ,c)2(r,a,b).b. A a*b*c*=anbncn|n 0,若A是上下文无关的，则由a中命题知 anbncn|n 0也是上下文无关的，矛盾。证明：设G是一个Chomsky范式CFG则对任一长度2的字符串w L(G),0的任何派生恰好有2n 1步。证明：(用数学归纳法)当n=2时，对于Chomsky式CFG长度为2的字 符串必由3步派生，此时命题为真。假设当2 n k时命题为真。当n=k+1时，对于长度为k+1的字符串 S=S1S2 Sk+1,存在 &的一个直接派生 So AB,使得A产生子用S1S2 sp, B产 生子用Sp+iSp+2 sk+1,其中1 p k+1。由归纳假设，A产生子用SiS2 Sp需要 2p-1步派生，而B产生子用Sp+iSp+2 Sk+1需要2(k+1-p)-1 步派生。因此，& 产生字符串s共需2(k+1)-1步派生。即当n=k+1时命题亦真。因此，由G产生长度为n 2的字符串需要2n-1派生。用泵引理证明下述语言不是上下文无关的：a. 0n1n0n1n| n 0假设语言上下文无关，设p为泵长度，取S=CP1p0p1p.由泵引理知，S可以 划分为uvxyz且满足泵引理条件。考察子用vxy,首先，它一定横跨S的中点， 否则，若vxy位于S的前半段，由于|vxy| p,则uv2xy2z中1将是后半段字 符串的第一个字符，即不可能是0n1n0n1n的形式。同理，vxy也不可能位于S后半段的位置上。但是，若vxy跨越S的中点时，将S抽取成uxz,它形如 0p1i0j1p,i , j不可能都为p,即uxz不可能是0rT0rT的形式。综上，可知S不能被抽取，因此，该语言不是上下文无关的。b. 0 n#02n#03n| n 0假设语言上下文无关，设p为泵长度，取S=0#02P#03p,由泵引理知，S可 以划分为uvxyz且满足泵引理条件。考察子用vxy。首先，v,y中不能有#,否 则S抽取成uxz后，其中#个数1。由条件3, vxy或者位于第2个#之前，或 者位于第1个#之后。下面讨论这两种情况： .此时，uv2xy2z中第3部分0的个数保持不变，而前面部分 的0的个数至少有一个增加，因此，uv2xy2z不在该语言中。 .此时，uv2xy2z中第1部分0的个数保持不变，而第2,3 部分0的个数至少有一个增加，也有 uv2xy2z不在该语言中。因此，该语言不是上下文无关的。c. w#x | w,x a,b *, w 是 x 的子用假设该语言上下文无关，设 p为泵长度，取S=0T#0P1P,由泵引理知，S 可以划分为uvxyz且满足泵引理条件。显然，v,y中不包含#,不然抽取后的 S=uxz中将不含#从而不在该语言中。子用vxy不能落在#的左侧，否则uv2xy2z中#左侧的字符串长度将大于右 边。子用vxy不能落在#的右侧，否则uxz中#左侧的字符串长度也会大于右边。现在假设# x,则必存在不全为0的i,j，使得vy=1i0j,下面分两种情况 考虑： .j 0,则uxz=0p1p-i#0P-j 1P不在该语言中 .j=0,则uv2xy2z中#左侧的字符串长度大于右边，不在 该语言中。因此，该语言不是上下文无关的。d. x i#X2# #xk | k 2,每一个 xi a,b,且存在 xi =xj假设该语言上下文无关，设 p为泵长度，取S=aV#aPbP,由泵引理知，S 可以划分为uvxyz且满足泵引理条件。显然，v,y中不包含#,不然抽取后的 S=uxz中将不含#从而不在该语言中。子用vxy不能落在#的左侧，否则uv2xy2z中#左侧的字符串长度将大于右 边。子用vxy不能落在#的右侧，否则uxz中#左侧的字符串长度也会大于右边。于是vxy跨越#两侧.此时，S经抽取成uxz后，具有apbi#ajbp的形式，其 中，i,j不全为p。因此，uxz不在该语言中。综上该语言不是上下文无关的。考虑语言B=L(G),其中G是练习中给出的文法。定理关于上下文无关语 的泵引理称存在关于B的泵长度p。p的最小值等于多少要求给出证明。证明：p的最小值为4。令D=0i#0j#0T1, j, k 0,E=0i#02i | i 0, 则L(G)=D EoL(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。设G是一个含有b个变元的乔姆斯基范式 CFG证明：如果G产生某个 字符串使用了至少2b步的派生，则L(G)是无穷的。T证明：设G产生字符串S需要至少2b步。由于一个分支点(变元)对应一次派生，所以 S 的语法树P至少有2b个分支点。又由于在乔姆斯基 范式下，一个分支点至多有两个子分支点(这意味着 层数 n的结点个数 2b- 1),从而的由分支点组 成的子树的高度大于等于b+1。有一条路径上分支 点(变元)个数 b+1。由鸽巢原理：必有某个变元 R 在该路径上出现至少两次。不妨假设 R出现在路径 上最下面的b+1个变元中。按上图所示，将S划分为uvxyz,在每一个R的下面有一棵子树，它产生 S的一部分。上面的R有一棵较大的子树，产生vxy,下面的R有一棵较大的 子树，产生x,由于这两棵子树由同一个变元产生，因而可以相互替换。这里 采用如下操作：反复用较大子树去替换较小子树，则我们得到对于任意n1, uv nxy nz L(G)。所以若我们能证明v,y不全为则L(G)是无穷的。事实上，由乔姆斯基范式的特点，上面一个R的派生选择的必为 R AB形式的规则，而且不可能有A 和B，所以v,y不全为。从而命题得证。给出一个语言，它不是上下文无关的、但满足泵引理的三个条件。要求 给出证明。解：令 A= aibjckdl | i,j,k,l 0,且当 i=1 时，j=k=l,则：(1) A满足泵引理的三个条件。取泵长度p= 1。对A中任意长度大 于1的字符用s= aibjckdl ,分情况可以如下抽取：若 i=1,贝U j=k=l, M v=a,uxy=, z= bjcjdj,贝取寸 n 0, uvnxynz=ai bj cj dA;若i 2,且j,k,l 不同时为0,不妨设j 0,取u=ai,v=b,xy=,z= bj-1 ckdl,贝U对 n 0, uvnxynz= aibj-1+nckdlA；若 i 2,且 j=k=l=0, 取 u=ai-1 ,v=a,xyz= ,贝U对 n 0, uvnxynz= ai-1+n A；若 i=0,则 j,k,l 不同时为 0,不妨设 j 0,M v=b,uxy=,z= bj-1 ckdl,贝取寸 n 0, uvnxynz=bj-1+nckdlA。(2) A不是上下文无关语言。事实上，若 A为上下文无关语言，另 取正则语言 R=abc*d*,由问题可知，L R是上下文无关的。但这与 L R=abncndn | n0不是一个上下文无关语言矛盾。因此， A不是上下文无关的。