计算理论习题解答

计算理论习题解答练习图给出两台和的状态图.回答下述有关问题1.1DFAM1M2.的起始状态是M1q1的接受状态集是M1{q2}的起始状态是M2q1的接受状态集是{M2q1,q4}对输入经过的状态序列是e.aabb,M1q1,q2,q3,q1,q12接受字符串吗？否M1aabb3接受字符串&吗？是M2给出练习中画出的机器和的形式描述1.22.1M1M2.其中M1=(Q1,NS1,q1,F1)1)Q1={q1,q2,q3,};2)当{a,b};SI为：abqqq121q2q3q3q3q2q1是起始状态q1F1={q2}其中M2=(Q2,N§2,q2,F2)2Q2={qI,q2,q3,q4}；32={a,b};为：482abq1q1q2q2q3q4q3q2q1q4q3q45是起始状态q26F2={q1,q4}的形式描述为其中」在 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 中给出。DFAM({qi,q2,q3,q4,qs},{u,d},S,q3,{q3}),2-3试画出此机器的状态图。1画出识别下述语言的DFA的状态图。a){w|w从1开始以0结束}1二】。，-可编辑-10一。,1j){w|w至少含有个且至多含有个20,11}m）空集n）除空串外的所有字符串、二。,1一y0,11给出识别下述语言的NFA,且要求符合规定的状态数。a.{w|w以00结束},三个状态0.1b.语言{w|w含有子串0101,即对某个x和y,w=x0101y}c.语言{w|w含有偶数个0或恰好两个1},6个状态。d.语言{0},2个状态。f.语言{&},1个状态。g.语言0*,1个状态。证明每一台NFA都能够转换成等价的只有一个接受状态的NFA。证明:设添加一个状态后，分别向弓屋箭头，将NFAM={Q,2,q0,F},F={rii,……，rik}.prii,……，rikpr，r变为非接受状态，p变为接受状态。又因为添加箭头不影响NFA识别语言，所以命题成立。ii,……ik£1)a证明：设M是一台语言B的DFA,交换M的接状态与非接受状态得到一台新的DFA,则这台新的DFA是识别B的补集，因此，正则语言类受在补运算下封闭。b举例说明：设M是一台识别语言B的NFA,交换M的接受状态与非接受状态得到一台新的NFA,这台新的NFA不一定识别B的补集。NFA识别的语言类在补集下封闭吗？解释你的回答。解：a.M是DFA,M是{Q,MS,qo，F},令N={Q,乙8,q0,Q-F},设«=coi32…con是字母表上任意字符串，因为与均为所以必然存在中状态序列使得：口，MNDFA,Qr0,r1,…nrr0=q0,8（wi+1）=ri+1,i=0,…,n-1若则31）rnFB;2）若rnF则rnQ-F,即N接受④，若coB,所以N接受B的补集，即B的补集正则。所以，正则语言类在补运算下封闭。b.设B为{0}。NFAM:可识别它。依题对它作变换，得到N:则N识别的语言{*不是B的子集。所以交换M的接受状态与非接受状态得到的新的NFA不一定识别B的补集。但是由于NFA识别的语言类与DFA识别的语言类相同，即正则语言类。由a的证明，正则语言类在补运算封闭，可知，NFA识别的语言类---正则语言类在补运算下封闭。若NFA识别语言A,必有等价的DFA识别A,从而由a知，可交换DFA的接受与非接受状态构造识别A的补集的DFA,则必有等价的NFA识别A的补集。只是，该NFA未必有原NFA交换接受与非接受状态构造而成。1.给出一个反例，说明下述构造不能证明定理2.24,即正则语言类在星号运算下封闭。设N=(Qi,2,识别。如下构造。应该识别。Si,qi,Fi)AiN=(Qi,"Si,qi,Fi)NAi*的状态集是的状态集。NNi的起始状态是的起始状态相同。NNi(q,a),F或a(q,a)i若(q,a){qi},qFja。的接受状态是原来的接受状态加上它的起始状态。F={qi}UFiF定义如下：对每一个属于和每一个属于d.8qQa2Ni:N:解：设识别语言{至少含有一个其中输入字母表为可知{空串或至少含有一个。NiA=i},{0,i},A*=i}按上述规定构造N的状态图如上。可以看出L(N)={0,i}*不等于A*.所以如此构造的N不一定识别A*.1.使用定理2.i9中给出的构造，把下图中的两台非确定型有穷自动机转换成等价的确定型有穷自动机。-可编辑-aaa),b)，解：a),b)1)给出生成练习2.4中语言的正则表达式。(注： 答案 八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案 不唯一)4){w|w从1开始以0结束}12*0.5){w|w至少有3个1}£1£1£1寸.6){w|w含有子串0101}£0101£.7){w|w的长度不小于3,且第三个符号为0}2十£.8){w|w从0开始且为奇长度，或从1开始且为偶长度}0(2E1式21.9){w|w不含子串110}(010)*1*.10){w|w的长度不超过5}2211){w|w是除11和111以外的任何字符}02*10£110£1112七12){w|w的奇位置均为1}(14*(1).13){w|w至少含有2个0,且至多含有1个1}0*(00010001100)014){仙.e0.15){w|w含有偶数个0.或恰好两个1}(1*01*0)*1*0*10*10*.16)空集..n.除空串外的所有字符串2-1.19对下述每一个语言，给出4个字符串,个是这个语言的成员，2个不是这个语言的成员。这里假设1.21使用引理2.32中叙述的过程，把图2-38中的有穷自动机转换成正则表达式Oa)，b),b)解:a)a*b(aba**b)(ab)ab[(aaabb)ab](a).子母表2={a,b}.a.a*b*成ab,aab非成aba,ba员：员：成非成b.a(ba)ab,abababb,aa员：员：成aa非成c.ab,bbbab,ba**员：a员：成aad.(aaa),aaaaaa非成员:a,aa*员：a成ab非成e.£a£b£a£,aabaaa,abb员：a员：成ab非成f.ababab,baba,b员：a员：成非成g.(a)bb,aba,bb员:员：非成成员：h.(ababb)2*a,bb员：，b（注：答案不唯一）1.29利用泵引理证明下述语言不是正则的。。A1={0n1n2n|n0}证明：假设是正则的。设是泵引理给出的关于的泵长度。AipAi令S=0P1P2P,是的一个成员且的长度大于所以泵引理保证可被分成段$=乂丫且满足泵引理的•.SAiSp,S32个条件。根据条件中只含中，比、多，不是的成员。违反泵引理的条件矛盾。33,y0,xyyz012xyyzAi1,不是正则的。.AiA2={www|w{a,b}*}.证明：假设是正则的。设是泵引理给出的关于的泵长度。A2pA2令S=aPbaPbaPb,是的一个成员且的长度大于所以泵引理保证可被分成段$=乂丫且满足泵引理的•.SA2SP,S32个条件。根据条件中只含所以中第一个的个数将比后两个的个数多，故不是的成员。33,ya,xyyzaaxyyzA2违反泵引理的条件i,矛盾。不是正则的。.A2在这里，表示一串个A3={a2n|n0}.（a2n2na.）证明：假设是正则的。设是泵引理给出的关于的泵长度。A3PA3令S=a2P,是的一个成员且的长度大于所以泵引理保证可被分成段$=乂丫且满足泵引理的•.SA2SP,S32个条件。即对任意的都应在中，且与的长度都应是的哥而且的长度应是的长度3i0,xyizA3xyizxyl+iz2.xyi+izxyiz的倍。于是可以选择足够大的使得但是2n（ni）i,|xyiz|=2n>P.即矛盾。|xyi+iz|-|xyiz|=|y|P.|xyi+iz|<2n+i,不是正则的。.A3i.30下面“证明”0T不是正则语言，指出这个“证明”中的错误。（因为0T是正则的，所以一定错误。）-可编辑-采用反证法证明。假设0*1*是正则的。令P是泵引定理给出的关于0*1*的泵长度。取S为字符串0P1P。S是0*1*的一个成员，但是例2.38已证明S不能被抽取。于是彳#到矛盾，所以0*1*不是正则的。解：在例中的语言是取为字符串确实不能被抽取；但针对语言2.38{0n1n|n0},S0P1P,S0*1*,是能被抽取的。将分成三段由泵引理的条件仅包含而属于语言*,即能被抽取，故题设SSS=xyz,3,y0,xyiz0*1S中的“证明”不正确。拒绝。图2—39是两台有穷状态状态转换器T2有穷状态转换器（）是确定性有穷自动机的一种类型。它的输出是一个字符串，而不仅仅是接受或1.24FSTFST的每一个转移用两个符号标记，一个指明该转移的输入符号，另一个指明输出符号。两个符号之间用斜杠“/”把它们分开。在中，从到的转移有输入符号和输出符号。某些转移可能有多对输TIq1q221入-输出，比如中从到它自身的转移。在对输入串计算时，从起始状态开始，一个接一个地TIq1FSTw取输入符号并且比照输入标记和符号序列进行转移。每一次沿一个转移走一步，输W1wn,W1wn=w出对应的输出符号。例如，对输入，机器依次进入状态和输出2212011T1q1,q2,q2,q2,q2,q1,q1,q1T1。对输入输出。给出在下述每一小题中机器进入的状态序列和产生的输出。1111000abbb,T21001对输入串输出：状态序列：1)T1011,000,q1,q1,q1,q1.对输入串输出：状态序列：2)TI211,111,q1,q2,q2,q2.对输入串输出：状态序列：3)TI0202,0101,q1,q1,q2,q1,q2o对输入串输出：状态序列：4)T2b,1,q1,q3.对输入串输出：状态序列：5)T2bbab,1111,q1,q3,q2,q3,q2.对输入串输出：状态序列：。6)T2bbbbbb,110110,qi,q3,q2,qi,q3,q2,qi对输入串输出：状态序列：7)T2，，q1o1.25给出有穷状态转换器的形式定义。解：有穷状态转换器FST是一个五元组(Q,N1,8,q0)1)Q是一个由穷集合，叫做状态集2)2是一个由穷集合，叫做输入字母表是一个由穷集合，叫做输出字母表3)P4)S:QXNQxr是转移函数是起始状态5)qoFST计算的形式定义：是一台由穷状态转换器，是输入字母表上的一个字符串。若存在M=(Q,NlS.qo)w=w1W2wn的状态序列：「和输出字母表上的一个字符串满足下述条件：041,rns=s1…sn,「1)0=q0;门,2)8(Wi+1)=(ri+1,Si+1),i=0,1,,n-1则M在W的输入下输出s.3利用你给练习的答案，给出练习中画出的机器和的形式描述。2.202.19T1T2解：有穷状态转换器的形式描述为:T1T1=({q1,q2},{0,1,2),6,q1,{0,1})其中转移函数为:012q1q1/0q1/0q2/1q2q1/0q2/1q2/1有穷状态转换器的形式描述为：T2T2=({{q1,q2,q3},{a,b},6,qi,{0,1})其中转移函数为：abq1q2/1q3/1q2q3/1q1/0q3q1/0q2/13给出一台具有下述行为的FST的状态图。它的输入、输出字母表都是{0,1}。它输出的字符串与输入的字符串偶数为相同、奇数位相反。例如，对于输入0000111,它应该输出1010010。1/10/0解：1/0明：假设{是正则的，是由泵引理给出的泵长度。取。由泵引理条件a)0nlm0n|m,n>0}ps=0p1q0p,q>03知，|xy|Wp,故y一定由0组成，从而字符串xyyz中1前后0的数目不同，即xyyz不属于该语言，这与泵引理矛盾。所以该语言不是正则的。b)假设{0n1n|n>0}的补集是正则的，则根据正则语言在补运算下封闭可得{0n1n|n>0}是正则的，这与已知矛盾，故假设不成立。所以该语言不是正则的。记c={0m1n|mwn},ic为c的补集，rcA0*1*={0n1n|n〃0},已知{0n1n|nR}不是正则的。若.c是正则的，由于0*1*是正则的，那么［cA0*1*也应为正则的。这与已知矛盾，所以.c不是正则的。由正则语言在补运算下的封闭性可知c也不是正则的。c){w|w{0,1}*不是一个回文}的补集是{w|w{0,1}*是一个回文}，设其是正则的，令p是由泵引理给出的泵长度。取字符串s=0plq0p,显然s是一个回文且长度大于p。由泵引理条件3知|xy|Wp,故y只能由0组成。而xyyz不再是一个回文，这与泵引理矛盾。所以{w|w{0,1}*是一个回文}不是正则的。由正则语言在补运算下的封闭性可知{w|w{0,1}*不是一个回文}也不是正则的。1.31对于任意的字符串w=ww23ww的反转是按相反的顺序排列w得到的字符串，记作wR,即1n,。对于任意的语言记证明：如果是正则的，则也是正则的。wR=wn…w2w1A,AR={wR|A}AAR证明：因为A是正则语言，所以可以用NFA来表示该语言，现在来构造AR的NFA,将NFAA中的接受态变为中间态，起始态变为接受态，再添加一新的起始态，并用箭头连接至原来的接受态，其它所有的箭头e反向。经过变换后得到NFA变成描述AR的NFA.1.32令'1]I1L1JJ包括所有高度为的和的列向量。上的字符串给出三行和的字符串。把每一行看作一个3301301二进制数，令最下面一行等于上面两行的和B={w3*|w}例如，0、r001,证明B是正则的。证明：由题设B的定义可知，w上面两行之和减去下面一行结果为零，由此可 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 NFAM(Q,N8,q0,F),其中。}。。状态表示上一次运算的进位为状态表示上一次运算的进位为。=3Q={q0,q1q0,q11因此是正则的。由题所以可知自动机M识别的是语言BR,BR2-24的结论可知B也是正则的。1.33令包含所有高度为的和的列。上的字符串名出两行和的字符串。把每一行看作一个二进2201201制数，令下面一行等于上面一行的倍}。C={w2*|w3证明C是正则的。可以假设已知问题2.24中的结果。证明：如下的状本率卜上一次运算的进位为NFA识别q0态寿示0,状态表示上一次运算的进位为状态表示上一次运算的进位为。q11,q22如下的1.34令的数的3倍余0,1,2的情况。包含所有高度为的和的列。上的字符串名出两行和的字符串。把每一行看作一个二进2201201制数，令上一行大于下一行}。D={w2*|w证明D是正则的。证明：由题设可设计自动机其中M=(Q,"8,q,F),Q={q1,q2},F={q2},转移函数与状态图为：00110101q1{q1}{q2}{q1}q2{q2}{q2}{q2}{q2}设汇与问题中的相同。把每一行看作和的字符串，令的下一行是上一行1.3522.2601E={w2*|w的反转},证明E不是正则的。证明：假设E是正则咯，令”是有泵引理给出的泵长度。’11[0\选择字符串s=。于是s能够被划分为xyz且满足泵引理的条件。「1[根据条件3,y仅能取包含〔Q4部分，当添加一个y时，xyyz不属于E.所以E不是正则的.是的整数倍}。证明对于每一个是正则的。Bn={ak|knn1,Bn证明：设字母表汇为则是一正则表达式。所以，也是正则表达式。由题意即{a},an(an)*Bn=(an)*,Bn可以用正则表达式表示。所以，也是正则的。Bn是一个二进制数，且是的整数倍}。证明对于每一个是正则的。Cn={x|xnn1,Cn证明：下面的识别(正向读)DFACn：M=(Q,{0,1},,q。，F),其中Q={0,1,2,…，n-1},i+1modn,(i,0)=(2imodn),i=0,1,2,…，n-1,起始状态为0,F={0}.这里i表示当前数modn余i.下面的识另(反向读)DFAijCnR：M=(Q,{0,1},,q0,F)，其中Q={(i,j)|i,j=0,1,2,…，n-1},((i,j),1)=(2imodn,(2i+j)modn),((i,j),0)=(2imodn,j),i,j=0,1,2,…，n-1起始状态为(1,0),F={(i,0)|i=0,1,…，n-1}.这里(i,j)表示当前数modn余j,而下一位所表示单位数modn余i(例如，若读下一位将达到k位,则下一位所表示单位数为10k-1).虑一种叫做全路径的新型有穷自动机。一台全路径是元组如果对*的每一个可能的NFANFAM5(Q,,,q0,F).Mx计算都结束在F中的状态，则M接受x。注意，相反的，普通的NFA只需有一个计算结束在接受状态，就接受这个字符串。证明：全路径NFA识别正则语言。证明：一个DFA一定是一个全路径NFA。所以下面只需证明，任意全路径NFA,都有一个与之等价的DFA。设有一全路径构造一个新与等价的全路径NFAN=(Q,RS,q0,F),NNFAN=(Q,q,F),i其i,NSi中oQ=Q{s},sQ。对于任意iqQi,aJ(q,a),qs,且S(q,a){s},qs,且S(q,a)=Si(q,a)={s},q=s.现在来构造一个与全路径等价的,N泗其中NFANiDFAM=(Q2qi,F2).即的所有子集组成的集合(也即的募集)；i)Q2=Power(Qi),QiQi定义函数为：对任意2)E:Q2Q2RQ2,E(R).i(r,);rR3)qi=E(q0);对于任意的属于属于"4)RQ2,a2(R,a)Ei(r,a).rR。5)F2={RQ2|RF}综上所述，DFA等价于全路径NFAoi.40如果存在字符串z使得xz=y,则称字符串x是字符串y的前缀。如果x是y的前缀且xwy,则称x是y的真前缀。下面每小题定义一个语言A上的运算。证明：正则语言类在每个运算下封闭。a)NOPREFIX(A)={3CA|3的任意真前缀都不是A的元素}b)NOEXTEND(A)={3CA|3不是A中任何字符串的真前缀}证明：假设DFAM=(Q,N8,q0,F)识别语言A。构造识别语言。其中，a)NFANi=(Q,"Si,q0,F)NOPREFIX(A){(q,a)},qQF,a;对任意(q,a),qF;qF,a2,i,qQ,a;所以，即NOPREFIX(A)为正则语言，亦即正则语言类A在NOPREFIX(A)运算下封闭。■构造识别语言。构造如下：b)NFAN2=(Q,N8,q0,F2)NOEXTEND(A)F2对中的任一接受状态若存在一条从它出发到达某接受状态(含本身)的路径，则将状态改为非Mqi,qi接受状态最后剩下的接受状态集记为所得的即识别。所以，；F2.NFAN2NOEXTEND(A)NOEXTEND(A)为正则语言，亦即正则语言类A在运算NOEXTEND(A)下封闭。■1.48证明：构造NFAN如下：O由于该NFA识别D,故D是正则语百。参见练习1.24中给出的有穷状态转换器的非形式定义。证明不存在FST对每一个输入w能够输出wR,其中输入和输出的字母表为{0,1}。证明：假设存在一台FST对每个输入w能够输出wR。则对于输入串W1=100,w2=101.该可分别输出,于是对于它的起始状态和输入字符会输出和两FSTw1R=001,W2R=1011,10个不同字符，这与FST是确定性有穷自动机相矛盾。所以，不存在一台FST对每个输入w能够输出wR。证明自反性。即对任意字符串这是因为对于每个字符串均有和同时是或不是的：1)x,xLXozxzxzL成员。对称性。即对任意字符串和若则。这是因为若则对于每个字符串2)xy,xLy,yLXxLy,z,xz和yz同时是或不是L的成员，那么yz和xz同时是或不是L的成员，于是yLX。传递性。即对任意字符串和若且则。这是因为对任意字符串由3)x,yz,xLyyLZ,xLZu,知和同时是或不是的成员，由知和同时是或不是的成员所以和同时是或不是xLyxuyuLyLZyuzuL，xuzuL的成员，此即xLZ。综上所述，是自反的，对称的，传递的，所以是一个等价的关系。L令方｛0,1,+,=｝和ADD=｛x=y+z|x,y,z是二进制整数，且x是y与z的和｝证明ADD不是正则的。证明：假设是正则白勺。设是泵引理给出的关于的泵长度。令为。于是能够被划分成且ADDPADDs1P=10P-1+1P-1sxyz,满足泵引理的条件。根据条件所以为。故不是正则的。3,y=1i,i>0.xyyz1P+i=10P-1+1P-1ADDADD证明：语言且若,则满足泵引理的个条件，虽然它不是正则的。解释这个事实为什么与F=｛aibjck|i,j,k0i=1j=k｝3泵引理不矛盾。证明：对任意正数p>1,设S是F中的一个成员且S的长度不小于p。将S分成3段S=xyz。此时。i=0,j=0.S=ck(k>0)取则对任意。x=,y=c,z=ck-1.i0,xyizFi=0,j>0.此时S=bjck(j>0,k0).取k则对任意。x=,y=b,z=bb1c.i0,xyizFi=1.此时S=abjck(j0,k0).取则对任意。x=,y=a,z=bjck.i0,xyizFi=2.此时S=a2bjck(j0,k0).取则对任意。x=,y=a2,z=bjck.i0,xyizF此时i>2.S=aibjck(i3,j0,k0).取则对任意。x=,y=a,z=ai-1bjck.i0,xyizF综上所述，语言F满足泵引理的3个条件。这一事实不与泵引理矛盾是因为泵引理是正则语言的必要不充分条件。求最小泵长度。0001*的最小泵长度为4.因为对任何s若|s|=3则s只含有0,不能被抽取。若时，把划分为为其余部分，则*。|s|>4sx=000y=1zxyiz00010*1*最小泵长度为1.若|s|R1时,S分两种情况：以开头，令为其余则S0x=,y=0,zxyiz0*1*.以开头，令为其余则S1x=,y=1,zxyiz0*1*.(01)*最小泵长度为2.若时，令为其余，则|s|>2x=,y=01,zxyiz(01)*.01,其最小泵长度为3。因为语言中只有有限个字符串时，任何一个字符串都不能被抽取。所以有限语言的泵长度为其最长字符串的长度加1。此时没有比泵长度长的字符串，前提假所以命题真。e.,其最小泵长度为1.理由类似于d中所述。证明：设对于每一个包含子串下面证明能被一台个状态的识别，而不能被只有2.39k>1,Ak={w|w1k-1}{1}*,A5kDFAk—1个状态的DFA识别。显然，能被个状态的AkkDFAM=({q1,q2,…,qk},{1},,q1，{qk}).识别，其中中(qi,1)=q(i=1,2，…,k-1),(q4,1)=q9假设A,可以被只有k-1个状态的DFAMI识别。考虑这样一个输入串s=1k-1,设M识另ijs的状态序列是r],匚,…%由于M的状态只有k-1个，根据鸽巢原理，r1,r2,…,rk中必有两个重复的状态，假设是r=rj(0i1,存在Ag使得AK能被K个状态的DFA识别，而不能被只有k-1个状态的DFA识别。略。利用语言和以及例证明上下文无关语言在交a.A={ambncn|m,n0}A={anbncm|m,n0}3.20,的运算下不封闭。b.利用(a)和DeMorgan律(定理1.10),证明上下文无关语言在补运算下不封闭。证明：a.先说明A,B均为上下文无关文法，对A构造CFGCISaS|T|TbTc|对构造B,CFGC2SSc|R|RaRb由此知A,B均为上下文无关语言。但是由例3.20,AAB={anbncn|n0}不是上下文无关语言，所以上下文无关语言在交的运算下不封闭。b.用反证法。假设CFL在补运算下封I<则对于（a）中上下文无关语言A,B,A,B也为CFL,且CFL对并运算封闭，所以AB也为CFL,进而知道AB为CFL,由DeMorgan定律其后=AAB,由此AAB是CFL,这与（a）的结论矛盾，所以CFL对补运算不封闭。略。和2.5给出产生下述语言的上下文无关文法和PDA,其中字母表={0,1}。{w|w至少含有3个1}S-A1A1A1AA一0A|1A|Sf0A0|1A1Af0A|1A|c.{w|w的长度为奇数}Sf0A|1A{w|w以相同的符号开始和结束}0,A一0B|1B|1,Bf0A|1Ad.｛w|w的长度为奇数且正中间的符号为0｝Sf0S0|1S1|0S1|1S0|0e.{w|w中1比0多}100:1f.{w|w=wR}Sf0S0|1S1|1|00,00,0g.空集2.6给出产生下述语言的上下文无关文法：a.字母表｛a,b｝上a的个数是b的个数的两倍的所有字符串组成的集合。S-bSaSaS|aSbSaS|aSaSbS|b.语言｛anbn|n0｝的补集。见问题3.25中的CFG:SfaSb|bY|TaTfaT|bT|{w#x|w,x{0,1}*且wR是x的子串}。SfUVUf0U0|1U1|WWfW1|W0|#Vf0V|1V|每一个且存在和使得}。d.{x1#x2##xk|k1,xi{a,b}*,ijxi=xjRSfUVWUfA|AfaA|bA|#A|#VfaVa|bVb|#B|#BfaB|bB|#B|#WfB|2.8证明上下文无关语言类在并，连接和星号三种正则运算下封闭。a.AB方法一：。设有和且。构造CFGCFGGI=(QI,,RI,SI)G2=(Q2,,R2,S2)L(GI)=A,L(G2)=BCFGG=(Q,,R,S。)，其中是起始变元，Q=Q1Q2{SO},SOR=RIR2{S0SI⑼}.方法二：PDA。设识别是识别。PI=(QI,,1,1,q1,F1)A,P2=(Q1,,2,2,q2,F2)B则如下构造的识别其中P=(Q,,,,qo,F)AB,是状态集，Q=QiQ2{q0}是栈字母表，=i2,是起始状态，qo是接受状态集，F=FiF2是转移函数，满足对任意qQ,a,b{(q,),3,)},若qq,ab,io(q,a,b),若qQ,b(),ii1(q,a,b)="(q,a,b),右qQ,b(),,else.222b.连接AB方法一：。设有和且。构造CFGCFGGi=(Qi,,Ri,Si)G2=(Q2,,R2,S2)L(Gi)=A,L(G2)=BCFGG=(Q,,R,S。)，其中是起始变元，Q=Q1Q2{SO},S0R=RiR2{S0S1S2}.方法二：PDA。设识别是识别而且满足在接受之前排空Pi=(Q1,,1,i,qi,Fi)A,P2=(Q1,,2,2,q2,F2)B,Pi栈(即若进入接受状态，则栈中为空)这个要求。则如下构造的识别其中P=(Q,,,,qi,F)AB,是状态集，Q=Q1Q2是栈字母表，=12,是起始状态，qi是接受状态集，F=FiF2是转移函数，满足对任意qQ,a,b若qQiFi,b(i)若qF,ab,i(q,a,b),i若qFi,(a,b)(,),(q,a,b){(q,)).i2若qQ2,b(2),(q,a,b)=(q,a,b),ielsec.2(q,a,b),方法一：。设有。构造其中CFGCFGGi=(Qi,,Ri,Si),L(Gi)=ACFGG=(Q,,R,So),Q=Qi{So},是起始变元，SoR=Ri{SoSoSo|Si|}.方法二：PDA。设识别而且满足在接受之前排空栈(即若进入接受状态，则栈中为空Pi=(Qi,,i,i,qi,Fi)A,Pi)这个要求。则如下构造的识别*,其中P=(Q,,,,qi,F)A是状态集,Q=Qi{qo}是栈字母表,=i,是起始状态,qo是接受状态集,F=Fi{qo}是转移函数，满足对任意qQ,a,b若qQiFi,i(q,a,b),i(q,a,b){(qi若qFi,ab,,)},(q,a,b)=i(q,a,b),若qFi,(a,b)(,),(qi,)若qqo,ab,证明在节开始部分给出的文法中,字符串2.93.iG2thegirltouchestheboywiththeflower有两个else不同的最左派生，叙述这句话的两个不同意思。＜句子＞名词短语><动词短语>复合名词><动词短语>冠词><名词><动词短语>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_<冠词><名词>agirltouchestheboywiththe<名词>agirltouchestheboywiththeflower含义是：女孩碰这个带着花的男孩<句子><名词短语><动词短语><复合名词><动词短语><冠词><名词><动词短语>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含义是：女孩用花碰这个男孩给出产生语言且或者或者的上下文无关文法。你给出的文法是歧义的吗?A={aibjck|i,j,k0i=jj=k}为什么？解：下面是产生A的一个CFG:UV|ABaUb|cV|aA|BbUc|这个CFG是歧义的，因为字符串abc有如下两种不同的最左派生：SUVaUbVabVabcVabcSABaAVaVabVcabc给出识别2.10中语言A的下推自动机的非形式描述。解：其非形式描述为：此PDA有两个非确定性的分支：一个分支先读a,并且每读一个a将一个a推入栈中，当碰到b时，每读一个b从栈中弹出一个a,若没有a可弹出则拒绝，最后读c且不改变栈中的内容，若此时栈为空则接受。另一个分支也是先读a,但不改变栈中内容，当碰到b时，每读一个b将一个b推入栈中，再读c,每读一个c从栈中弹出一个b,若没有a可弹出则拒绝，若c读完后栈为空则接受。开始时，读输入串的字符，非确定性的选择一个分支运行，若有一个分支接受则接受，否则拒绝。设有上下文无关文法G:STT|UU0U00|#T0T|T0|#a.用普通的语言描述L(G)。b.证明L(G)不是正则的。解：。a.A={0i#0j#0k|i,j,k0}{0i#02i|i0}取则对于任意划分所以不是正则的。b.s=0p#02p,s=xyz(|xy|p,|y|>0),xynz=0p+i#02pA,用定理2.6中给出的过程，把下述CFG转换成等价的乔姆斯基范式文法。ABAB|B|B00去掉BB00|S0A解：添加新起始变元So,ABAB|AB|BA|B|SoAB00ABAB|B|B00|去掉ABS0A去掉A,ABAB|AB|BA|00|BBS0AB00ABAB|AB|BA|B|BBB00添加新变元S0VB|AB|BA|UU|BB去掉S0A,AVB|AB|BA|UU|BBS0BAB|AB|BA|00|BBBUUABAB|AB|BA|00|BBVBA2.x先说明如何把正则表达式直接转换成等价得上下文无关文法，然后利用问题xxx的结果,给出每一个正则语言都是上下文无关文法的一个证明。解：设有正则表达式T,将其转化为上下文无关文法。1）首先添加ST,且令S为起始变元。2）根据T的不同形式，按如下方式添加规则.若T=a则在规则集中添加Ta,.若T=,则在规则集中添加T,.若T=,则在规则集中添加TT,.若T=AB,则在规则集中添加TA|B,.若丁=人8,则在规则集中添加TAB,.若T=A*,则在规则集中添加TA,和AAA|3)若有新添加的变元，则根据其所对应的表达式转第2步，直到没有新的变元出现。下面来证明每一个正则语言都是上下文无关的由正则语言与正则表达式的等价性可知：对于一个正则语言都存在一个描述他的正则表达式，由前述讨论可知，这个正则表达式可转换为一个与之等价的上下文无关的文法。因此，此正则语言能由这个上下文无关文法产生。所以正则语言是上下文无关的。2.18a.设C是上下文无关语言，R是正则语言。证明语言CR是上下文无关的。b.利用a证明语言且含有数目相同的A={w|w{a,b,c)*,a,b,c)证明：设是一个识别的是识别的一台。下a.P=(Qi,,,i,qi,Fi)CPDA,N=(Q2,,2,q2,F2)RNFA面构造识别的如下CRPDAS=(Q,,,,q0,F):是状态集，Q=Q1XQ2,是起始状态，q0=(q1,q2)是接受状态集，F=F1XF2,是转移函数，满足对任意qQ1,rQ2,a,b,((q,r),a,b)={((q',r'),c)|q'1(q,a),(r',c)2(r,a,b)}.若是上下文无关的，则由中命题知也是上下文无关b.Aa*b*c*={anbncn|n0},Aa{anbncn|n0}-可编辑-的，矛盾。2.26证明：设G是一个Chomsky范式CFG,则对任一长度2的字符串wL(G),w的任何派生恰好有2n—1步。证明：(用数学归纳法)当n=2时，对于Chomsky范式CFG,长度为2的字符串必由3步派生，此时命题为真。假设当时命题为真。当时，对于长度为的字符串,存在的一个直接派生使得产生子串2nkn=k+1k+1s=siS2sk+iS0SOAB,ASIS2sp,B产生子串，其中。由归纳假设，sp+1sp+2sk+11pk+1产生子串需要步派生，而产生子串需要步派生。因此，产生字符串共需ASIS2SP2p-1BSP+Isp+2sk+12(k+1-p)-1SOs2(k+1)-1步派生。即当n=k+1时命题亦真。因此，由G产生长度为n2的字符串需要2n-1派生。2.30用泵引理证明下述语言不是上下文无关的：{0n1n0n1n|n0}假设语言上下文无关，设p为泵长度，取S=0p1p0Plp.由泵引理知，S可以划分为uvxyz且满足泵引理条件。考察子串vxy,首先，它一定横跨S的中点，否则，若vxy位于S的前半段，由于|vxy|p,则uv2xy2z中1将是后半段字符串的第一个字符，即不可能是0n1n0n1n的形式。同理，vxy也不可能位于S后半段的位置上。但是，若跨越的中点时，将抽取成它形如不可能都为即不可能是的形式。vxySSuxz,0Pli0j1p,i,jp,uxz0n1n0n1n综上，可知S不能被抽取，因此，该语言不是上下文无关的。{0n#02n#03n|n0}假设语言上下文无关，设p为泵长度，取S=0p#02P#03p,由泵引理知，S可以划分为uvxyz且满足泵引理条件。考察子串vxyo首先，v,y中不能有#,否则S抽取成uxz后，其中#个数1。由条件3,vxy或者位于第2个#之前，或者位于第1个#之后。下面讨论这两种情况：.此时，uv2xy2z中第3部分0的个数保持不变，而前面部分的0的个数至少有一个增加，因此,uv2xy2z不在该语言中。.此时，uv2xy2z中第1部分0的个数保持不变，而第2,3部分0的个数至少有一个增加，也有uv2xy2z不在该语言中。因此，该语言不是上下文无关的。是的子串{w#x|w,x{a,b}*,wx}假设该语言上下文无关，设p为泵长度，取S=0p1p#0p1p,由泵引理知，S可以划分为uvxyz且满足泵引理条件。显然，v,y中不包含#,不然抽取后的S=uxz中将不含#从而不在该语言中。子串vxy不能落在#的左侧，否则uv2xy2z中#左侧的字符串长度将大于右边。子串vxy不能落在#的右侧，否则uxz中#左侧的字符串长度也会大于右边。现在假设则必存在不全为的使得下面分两种情况考虑：#x,0i,j,vy=1'0j,.j0,则uxz=0p1p-i#0p-j1p不在该语言中.j=0,则uv2xy2z中#左侧的字符串长度大于右边，不在该语言中。因此，该语言不是上下文无关的。每一个且存在{x1#x2##xk|k2,xi{a,b}*,xi=xj}假设该语言上下文无关，设p为泵长度，取S=apbp#apbp,由泵引理知，S可以划分为uvxyz且满足泵引理条件。显然，v,y中不包含#,不然抽取后的S=uxz中将不含#从而不在该语言中。子串vxy不能落在#的左侧，否则uv2xy2z中#左侧的字符串长度将大于右边。子串vxy不能落在#的右侧，否则uxz中#左侧的字符串长度也会大于右边。于是跨越两侧.此时，经抽取成后，具有的形式，其中，不全为。因此，vxy#Suxzapbi#ajbpi,jpuxz不在该语言中。综上该语言不是上下文无关的。考虑语言B=L(G),其中G是练习3.13中给出的文法。定理3.19关于上下文无关语的泵引理称存在关于B的泵长度p。p的最小值等于多少？要求给出证明。证明：的最小值为。令贝。p4D={0i#0j#0k|i,j,k0},E={0i#02i|i0},UL(G)=DEL(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)是无穷的。证明：设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,uvnxynzL(G)。所以若我们能证明v,y不全为,则L(G)是无穷的。£事实上，由乔姆斯基范式的特点，上面一个R的派生选择的必为RAB形式的规则，而且不可能有A和B,所以v,y不全为。从而命题得证。2.26给出一个语言，它不是上下文无关的、但满足泵引理的三个条件。要求给出证明。解：令A={a'bjckd1|i,j,k,l0,且当i=1时，j=k=l},则：满足泵引理的三个条件。取泵长度。对中任意长度大于的字符串Ap=1A1s=a'bjckd1,分情况可以如下抽取：若则取贝对i=1,j=k=1,v=a,uxy=,z=bjcjdj,Un0,uvnxynz=a'bjcjdjA;若且不同日^为不妨设取则对i2,j,k,10,j0,u=a',v=b,xy=,z=bj-1ckd1,n0,uvnxynz=aibj-1+nckd1A;若i2,且j=k=1=0,取u=ai-1,v=a,xyz=,则对n0,uvnxynz=ai-1+nA;若则不同日寸为不妨设取j-1k1则对n+nk1。i=0,j,k,10,j0,v=b,uxy=,z=bcd,n0,uvnxyz=bb1cdAA不是上下文无关语言。事实上，若A为上下文无关语言，另取正则语言R=ab*c*d*,由问题3.17可知，LR是上下文无关的。但这与LR={abncndn|n0}不是一个上下文无关语言矛盾。因此，A不是上下文无关的。3.3修改定理3.10以得到推论3.12的证明，即证明一个语言是可判定的当且仅当有非确定的TM判定它。证明：若M是一个确定型判定器则，则M也是一个非确定型判定器。-可编辑-现在设N是一个非确定的判定器，将构造一个与之等价的确定型判定器M。模拟过程使用深度搜索。设N的不确定性分支的最大个数为boM有三个带：一个输入带，一个工作带，一个地址带。M按深度优先方式搜索N的不确定计算分支树。M="输入w,1)初始化，第一带上为w,第二带为空，第三带为1;2)将第一带的内容复制到第二带上，按当前地址位数字选择N的一个不确定性分支，在第二带上模拟N运行一步；若当前地址位为i 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 S的当前状态，并且栈B的栈顶字符为S的读写头所指方格的字符：a）若S执行一个右移（q,a）=（r,b,R）,则将栈B的栈顶字符a替换为b,弹出b,推入栈A,记录S的当前状态r。b）若S执行一个左移（q,a）=（r,b,L）,首先将栈B的栈顶字符a替换为b;若栈A不空，则将栈A弹出一个字符推入栈B;若栈A为空（对应于S处于工作带最左端），则不作栈操作。记录S的当前状态r。3）若S进入接受状态，则进入接受状态。”由上知.我们用2-pda模拟了图灵机，所以2-pda比1-pda强大.下面用一个四带TMS来模拟一个3-pdaP,要求P进入接受状态之前排空栈，并且或者推入或者弹出：记P的三个栈为A,B,CoS的四个带，第一带用来模拟P的输入带，第二，三，四带分别模拟栈A,B,C:S="对于输入字符串w,1)初始化，第一带放入w,第二，三，四带为空。模寸P分别在四个带上按如下方式动作：a.若P在输入带上读一个非空字符，则读第一带字符并右移一格；若P在输入带上读一个，则在第一带上不读字符，且读写头保持不动。b.栈A,B,C中若有弹出，则在相应带上当前格改写为空格，并左移一格；若有推入a,则在相应带上右移一格，并写入a。若P进入接受状态，则接受。”3.10证明双无限带图灵机识别图灵可识别语言。证明思路：利用双无限单带图灵机模拟普通单带图灵机时，只需要设计一个左端点。我们的证明是让它在第一格左边标记“$”作为左端点。证明：首先用单带双无限带图灵机模拟普通单带图灵机：设有普通图灵机=()。下面构造与之等价的单带双无限带图灵M1Q1,,1,1,q0,qaccept,qreject机其中M2=(Q2,,2,2,qs,qaccept,qreject),为新的起始状态；Q2=Q1{qs,qt},qs2=1{$}.对任意qQ2,a2,(q,a,L),右qq,ts(qc$,R),若qq,(q,a)(q,a),右qQt,a2,ii1(q,$,R),若qQ,a$.i再用普通单带图灵机模拟单带双无限带图灵机：设有单带双无限图灵机下面构造普通单带图灵机：M1=(Q,,,,qo,qaccept,qreject),M2"输入串M2=W,1)将带上字符串改写为$w,将读写头放在W的第一个字符上，按照的转移函数运行，2)Mi3)每当读写头移到了$上，就将$右边的所有字符右移一格，并在$右边的方格里写上空格符,再将读写头放在这个方格上，转第二步，4)若进入接受状态，则接受；若进入拒绝状态则拒绝。”也可以用普通双带图灵机模拟单带双无限带图灵机：设有单带双无限图灵机下面构造普通双带图灵机：M1=(Q,,,,qo,qaccept,qreject),M2"输入串M2=W,1)在第一个带上放上$,读写头放在$上；第二个带子上放入#W,读写头放在第二个方格上。当第一带读写头位于$上，而第二带读写头不在#上时，在第二带上按照的转移规则运行,2)M1直到停机或读写头移到#上。若进入接受状态则接受，若进入拒绝状态则拒绝。若读写头移到#上，则将第一带上读写头右移一格。当第二带读写头位于#上，而第一带读写头不在上时，在第一带上按照的转移规则运行，但是每一步要3)$M1将读写头移动方向反向，直到停机或读写头移到$上。若进入接受状态则接受，若进入拒绝状态则拒绝。若读写头移到$上，则将第二带上读写头右移一格，转第二步。”3.11只写一次图灵机是一个单带图灵机，它在每个带方格上最多只能改变其内容一次（包括带上得输入区域）。证明图灵机模型的这个变形等价于普通的图灵机模型。证明：普通单带图灵机总是可以模拟只写一次图灵机。下面说明怎样用一个只写一次TMT模拟一个普通单带TMS。"对于输入T=w=w1W2wn,在上并模拟运行。1）W1W2WnS2）每当S要改写工作带时（例如设S要将当前方格内容改写为b,并且左移或右移一格），T按如下方式动作：a.将当前方格改写为“b*”，在带子右边第一个空格写下“#"。b.将“#"左边的字符抄