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

《计算理论课后习题答案.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章习题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011

2、0A011B0C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

3、:S→ABC,A→aA

4、a,B→bB

5、b,C→cC

6、c(2)G=({S,A,B,C},{a,b,c},P,S)P:S→aA,A→aA

7、bB,B→bB

8、cC,C→cC

9、ε(3)G=({S},{0,1},P,S)P:S→0S0

10、1S1

11、00

12、11第二章习题1．设计一个有限自动机(FA)M，使得T(M)中的每个句子w同时满足下面三个条件：1)w∈{a,b,}*；2)

13、w

14、是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,…}解：

15、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]

16、[q1,q2,…,qi]∈K’且{q1,q2,…,qi}∩F≠Φ}δ’：K’×∑→K’，对[q1,q2,…,qi]∈K’,a∈

17、∑，有δ’([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

18、,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δ’：对任何q∈K,任何a∈∑,δ’(q,a)=(q,a)。解：M’=(K,∑,δ’,q0,F’)，q0是M的开始状态，其中公式(1)：对于q∈K,,(q,ε)=ε-

19、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(ε