计算理论课后习题答案.pptxVIP

第一章习题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试写出句派生过程。解：S?ABC?0ADC?0AB0C?01AE0C?01A0EC?01A0B1C?01AB01C?011AE01C?011A0E1C?011A01EC?011A01B1C?011A0B11C?011AB011C?0110AD011C?0110A0D11C?0110A01D1C?0110A011DC?0110A011B0C?0110A01B10C?0110A0B110C?0110AB0110C2．设计下列各文法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

P:S→aA,A→aA|bB,B→bB|cC,C→cC|εG=({S,A,B,C},{a,b,c},P,S)P:S→0S0|1S1|00|11G=({S},{0,1},P,S)

第二章习题1．设计一个有限自动机(FA)M，使得T(M)中的每个句子w同时满足下面三个条件：1)w∈{a,b,}*；2)|w|是3的整数倍；3)w以a开头，以b结尾。解：q0q1q3q2q4aa,ba,ba,bb

2．设计二个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]0100000010111111

4.将下面的ε-NFAM等价变换成NFAM’。abcdefε1εεε010δ’：对任何q∈K,任何a∈∑,δ’(q,a)=(q,a)。解：M’=(K,∑,δ’,q0,F’)，q0是M的开始状态，其中公式