计算理论课后习题答案

第一章习题1．给定文法G=({S,B,C,D,E},{0,1},P,S)，其中P：S→ABC，AB→0AD，AB→1AE，AB→ε，D0→0D，D1→1D，E0→0E，E1→1E，C→ε，DC→B0C，EC→B1C，0B→B0，1B→B1试写出句子01100110的派生过程。解：SABC0ADC0AB0C01AE0C01A0EC01A0B1C01AB01C011AE01C011A0E1C011A01EC011A01B1C011A0B11C011AB011C0110AD011C0110A0D11C0110A01D1C0110A011DC0110A011B0C0110A01B10C0110A0B110C0110AB0110C01100110C011001102．设计下列各文法G，使得它们分别是：（1）G是个上下文无关文法，且L(G)={aibjck∣i,j,k≥1}。（2）G是个正规文法，且L(G)={aibjck∣i,j,k≥1}。（3）G是个上下文无关文法，且L(G)={wwR∣w∈{0,1}+}。其中wR是w的逆转，例如w=001,则wR=100.解：设计一个文法G要验证：凡是符合要求的句子G都能产生出来；G产生出来的所有句子都是符合要求的。(1)G=({S,A,B,C},{a,b,c},P,S)P:S→ABC,A→aA|a,B→bB|b,C→cC|c(2)G=({S,A,B,C},{a,b,c},P,S)P:S→aA,A→aA|bB,B→bB|cC,C→cC|ε(3)G=({S},{0,1},P,S)P:S→0S0|1S1|00|11第二章习题1．设计一个有限自动机(FA)M，使得T(M)中的每个句子w同时满足下面三个条件：1)w∈{a,b,}*；2)|w|是3的整数倍；3)w以a开头，以b结尾。解：q0q1q3q2q4aa,ba,ba,bb2．设计二个FAM1和M2，分别满足T(M1)={02i∣i是自然数}T(M2)={02i+1∣i=0,1,2,3,4,…}解：M1：q0q1q3000q1q000q0q100M2：3.给定NFAM1=({p,q,r,s},{0,1},δ,p,{s})，如下表所示。构造一个DFAM2，使得T(M1)=T(M2)。解：令M2=(K’,∑,δ’,q0’,F’),其中K’2K，K’中的元素是由K的子集{q1,q2,…,qi}构成，但是要把子集{q1,q2,…,qi}作为的一个状态看待，因此把此子集写成[q1,q2,…,qi]。q0’=[q0],F’={[q1,q2,…,qi]|[q1,q2,…,qi]∈K’且{q1,q2,…,qi}∩F≠Φ}δ’：K’×∑→K’，对[q1,q2,…,qi]∈K’,a∈∑，有δ’([q1,q2,…,qi],a)=[p1,p2,…,pj]当且仅当δ({q1,q2,…,qi},a)={p1,p2,…,pj}δ01p{p,q}{p}q{r}{r}r{s}Φs{s}{s}q0’=[p],K’和F’以后确定。δ’：δ01p{p,q}{p}q{r}{r}r{s}Φs{s}{s}[p]01[p,q][p][p,q][p,q,r][p,r][p,r][p,q,s][p][p,q,r][p,q,r,s][p,r][p,q,s][p,q,r,s][p,r,s][p,r,s][p,q,s][p,s][p,s][p,q,s][p,s][p,q,r,s][p,q,r,s][p,r,s]K’={[p],[p,q],[p,r],[p,s],[p,q,r],[p,q,s],[p,r,s],[p,q,r,s]}F’={[p,s],[p,q,s],[p,r,s],[p,q,r,s]}[p][p,q][p,r][p,q,r][p,q,s][p,r,s][p,s][p,q,r,s]01000000101111114.将下面的ε-NFAM等价变换成NFAM’。abcdefε1εεε010否则－如果ΦF)CLOUSURE(qεF}{qF{F00ˆδ’：对任何q∈K,任何a∈∑,δ’(q,a)=(q,a)。解：M’=(K,∑,δ’,q0,F’)，q0是M的开始状态，其中ˆ公式(1)：对于q∈K,,(q,ε)=ε-CLOSURE(q)公式(2)：对于q∈K,w∈∑*,a∈∑,ˆˆ(q,wa)=ε-CLOSURE(δ((q,w),a))因为fCLOSURE(a)={a,b},所以F’=F={f}δ’：q∈K,任何a∈∑,abcdefε1εεε010ˆδ’(q,a)=(q,a)。ˆ在计算(q,a)时，要将a理解成a路径！ˆ例如δ’(a,0)=(a,0)={c,e,d,b}。δ’:01abcdef{c,e,d,b}{d,b}Φ{d,b}{f}{f,d,b}{f}{d,b}{f}{f,d,b}ΦΦ5．化简正规表达式a(ε+aa)*(ε+a)b+b+φ(ab*+b)*。解：上式＝a(aa)*(ε+a)b+b其中(aa)*(ε+a)代表集合：{ε,aa,aaaa,aaaaaa,…}{ε,a}={ε,aa,aaaa,aaaaaa,…}{a,aaa,aaaaa,…}={ε,a,aa,aaa,aaaa,aaaaa,aaaaaa,…}={a}*于是上式＝aa*b+b=a+b+b=(a++ε)b=a*b6．构造一个FAM，使得T(M)的正规表达式为01+((0+1)*1)*。解：1.分解表达式，找出基本单元：0,1,01,1。设计接收这些基本单元的自动机如下：q1q20q3q41q7q81q5q60q9q1012.组装：（按照优先权从高到低）01+((0+1)*1)*q7q81q5q60q9q171q0εq15q10q16q12q2q10q3q41q14q13q11εεεεεεεεεεεεεεεεε7．给定FAM如下图所示，求它所接收的语言T(M)的正规表达式。解：q2q10011m)k(jq)k,aiq(δjimaaajimaaarij1}...21...21{01111*)(kijkkjkkkkikkijrrrrrε010ε1022021012011rrrr即可。和所以只求＝为的正规表达式接收的语言因为122112112122122112212*)(rT(M)Mrrrrrrrr0*10*)ε1(*)()ε)(()(*)(012011012011012012011012012011011112rrrrrrrrrrrrε0*1ε0)ε1(ε001ε00*11ε00*)ε1(1*)(022012011021122rrrrrε010ε1022021012011rrrr)0*1()*0*1(0*1)*ε0*1(0*1)*(ε))(()(*)(r122112122112112122112112122122112212rrrrrrrrrrrr＝8.将下面有限自动机简化(要求有简化过程)。解：一.定义K上等价关系给定DFAM=(K,∑,δ,q0,F)，p,q∈K,pq对x∈∑*,有δ(p,x)∈Fδ(q,x)∈F如果pq也称p与q是不可区分的。二.商集K/三．的逆关系̷p̷qx(x∈∑*∧(δ(p,x)∈Fδ(q,x)∈F))x(x∈∑*∧((δ(p,x)∈F∧δ(q,x)F)∨(δ(p,x)F∧δ(q,x)∈F)))x(x∈∑*，使得δ(p,x)与δ(q,x)恰有一个在F中)如果p̷q,称p与q是可区分的。判断p̷q是比较容易的。abcfed00,10001011114．判断可区分状态对的算法引理2-1设M=(K,∑,δ,q0,F)是DFA，则状态对(p,q)是可区分的(即p̷q)，当且仅当在下面算法中(p,q)格写上×。begin1．forp∈F,q∈K-F,do给(p,q)格写×；2．forF×F或(K-F)×(K-F)中每个状态对(p,q)(p≠q)，do3．ifa∈∑，使得格(δ(p,a),δ(q,a))内已经写上×，thenbegin4．给(p,q)格写×；5．如果刚刚写上×的格内有先前写入的状态对，此状态对的格同时也写入×。反复执行5,直到写入×的格内没有先前写入的状态对为止；endelse/**格(δ(p,a),δ(q,a))内无×**/6．for每个a∈∑,do7．把(p,q)写入格(δ(p,a),δ(q,a))内，除非δ(p,a)=δ(q,a)。end执行此算法的结果用一个表表示，实际上，执行此算法的过程就是向这个表内写入“×”的过程。abcdebcdef××××(b,d)abcfed00,1000101111××××(a,b):ab01be×××?××(a,c):ac01ba(a,d):ad01bfbd01cd01ef01bc01(b,c):(b,d):(c,d):(e,f):eaeffeafddfe得：bd,ef,aa,cc于是K/{{a},{b,d},{c},{e,f}}，五．构造简化的有限自动机定理2-5.1给定DFAM＝(K,∑,δ,q0,F)，可根据引理2-1中的算法构造出除去不可达状态的具有更少状态的DFAM’，使得T(M’)=T(M)。证明：先对M用引理2-1中的算法求出K/。再构造M’：M’=(K’,∑,δ’,[q0],F’)，其中K’={[q]|[q]∈K/且在M中q是从q0可达的状态}F’={[q]|q∈F}δ’：对任何[q]∈K’，任何a∈∑,δ’([q],a)=[δ(q,a)]K/{{a},{b,d},{c},{e,f}}={[a],[b],[c],[e]}，([b]=[b,d],[e]={e,f})K’={[a],[b],[c],[e]}F’={[e]}M’=(K’,∑,δ’,[a],F’)=({[a],[b],[c],[e]},{0,1},δ’,[a],{[e]})δ’([q],a)=[δ(q,a)]abcfed00,1000101111δ’:01[a][b][c][e][b][c][b][e][a][a][e][e][a][b]0[c]1[e]0,10,1019．给定DFAM如图所示。求一个左线性文法G，使得L(G)=T(M)。解：有两种方法。方法11.先将M逆转成M’：BAC10100,1BAC10100,1Sεε2.根据M’构造右线性文法G’：SA|C|εA0BB0A|0C|1C|0C1A|1B|13.将G’逆转成左线性文法G:SA|C|εAB0BA0|C0|C1|0CA1|B1|1P={qap|δ(q,a)=p}∪{qa|δ(q,a)∈F}。方法21.先根据M构造右线性文法G’：A0B|1C|1(其中A是开始变元)B0A|1C|0|1C0B|1B2.再将G’直接变成左线性文法G:根据定理：(1)Sα,当且仅当Sα∈P；(2)Aiα,当且仅当SαAi∈P；(3)AiAjα,当且仅当AjαAi∈P；(4)SAjα,当且仅当Ajα∈P。(1)由A1得:A1(2)由A0B得:B0由A1C得:C1(3)由B0A得:AB0由B1C得:CB1由C0B得:BC0由C1B得:BC1(4)由B0得:AB0由B1得:AB1BAC10100,1方法21.先根据M构造右线性文法G’：A0B|1C|1|ε(其中A是开始变元)B0A|1C|0|1C0B|1B因开始变元A出现在产生式右侧，故引入新的开始变元S，SA(其中S是开始变元)A0B|1C|1|εB0A|1C|0|1C0B|1BBAC10100,12.再将G’直接变成左线性文法G:根据定理：(1)Sα,当且仅当Sα∈P；(2)Aiα,当且仅当SαAi∈P；(3)AiAjα,当且仅当AjαAi∈P；(4)SAjα,当且仅当Ajα