您好,欢迎访问三七文档
当前位置:首页 > 建筑/环境 > 电气安装工程 > 计算理论课后习题答案
第一章习题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的派生过程。解:SABC0ADC0AB0C01AE0C01A0EC01A0B1C01AB01C011AE01C011A0E1C011A01EC011A01B1C011A0B11C011AB011C0110AD011C0110A0D11C0110A01D1C0110A011DC0110A011B0C0110A01B10C0110A0B110C0110AB0110C01100110C011001102.设计下列各文法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))因为fCLOSURE(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(δjimaaajimaaarij1}...21...21{01111*)(kijkkjkkkkikkijrrrrrε010ε1022021012011rrrr即可。和所以只求=为的正规表达式接收的语言因为122112112122122112212*)(rT(M)Mrrrrrrrr0*10*)ε1(*)()ε)(()(*)(012011012011012012011012012011011112rrrrrrrrrrrrε0*1ε0)ε1(ε001ε00*11ε00*)ε1(1*)(022012011021122rrrrrε010ε1022021012011rrrr)0*1()*0*1(0*1)*ε0*1(0*1)*(ε))(()(*)(r122112122112112122112112122122112212rrrrrrrrrrrr=8.将下面有限自动机简化(要求有简化过程)。解:一.定义K上等价关系给定DFAM=(K,∑,δ,q0,F),p,q∈K,pq对x∈∑*,有δ(p,x)∈Fδ(q,x)∈F如果pq也称p与q是不可区分的。二.商集K/三.的逆关系̷p̷qx(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.ifa∈∑,使得格(δ(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得:bd,ef,aa,cc于是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’:SA|C|εA0BB0A|0C|1C|0C1A|1B|13.将G’逆转成左线性文法G:SA|C|εAB0BA0|C0|C1|0CA1|B1|1P={qap|δ(q,a)=p}∪{qa|δ(q,a)∈F}。方法21.先根据M构造右线性文法G’:A0B|1C|1(其中A是开始变元)B0A|1C|0|1C0B|1B2.再将G’直接变成左线性文法G:根据定理:(1)Sα,当且仅当Sα∈P;(2)Aiα,当且仅当SαAi∈P;(3)AiAjα,当且仅当AjαAi∈P;(4)SAjα,当且仅当Ajα∈P。(1)由A1得:A1(2)由A0B得:B0由A1C得:C1(3)由B0A得:AB0由B1C得:CB1由C0B得:BC0由C1B得:BC1(4)由B0得:AB0由B1得:AB1BAC10100,1方法21.先根据M构造右线性文法G’:A0B|1C|1|ε(其中A是开始变元)B0A|1C|0|1C0B|1B因开始变元A出现在产生式右侧,故引入新的开始变元S,SA(其中S是开始变元)A0B|1C|1|εB0A|1C|0|1C0B|1BBAC10100,12.再将G’直接变成左线性文法G:根据定理:(1)Sα,当且仅当Sα∈P;(2)Aiα,当且仅当SαAi∈P;(3)AiAjα,当且仅当AjαAi∈P;(4)SAjα,当且仅当Ajα
本文标题:计算理论课后习题答案
链接地址:https://www.777doc.com/doc-3455562 .html