资源描述：
《形式语言答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章习题解答习题2.2.4a)1000111b)0,100011c)100,10110习题2.2.9a)对
2、w
3、作归纳法。当
4、w
5、=1时w为一字符，由题设已成立。设δˆ(q,w)=δˆ(q,w)，0f则对任一字母a，有δˆ(q,wa)=δˆ(δˆ(q,w),a)=δˆ(δˆ(q,w),a)=δˆ(q,wa).00ffkkb)对k作归纳法。k=1时，由题设命题已成立。设x∈L(A)，即δˆ(q,x)=q。0fk+1kk＋1于是δˆ(q,x)=δˆ(δˆ(q,x),x)=δˆ(q,x)=q，即x∈L(A)，证毕。00ff习题2.2.
6、101)将DFA改写成转移图形式：001A1B2）观察上图，知其接受的语言应为L＝{w∈{0,1}*:w含奇数个1}.3)用数学归纳法证明2）中的断言：当
7、w
8、=1时，若w＝0则DFA不接受w，若w＝1则DFA接受w，此时命题成立。设w时命题成立，即当w中含偶数个1时DFA不接受w，当w中含奇数个1时DFA接受w。对于任一字符c：若c=0，则当w中含偶数个1时由于DFA不接受w，故δˆ(q,w)=A，从而0δˆ(q,wc)=A；当w中含奇数个1时由于DFA接受w，故δˆ(q,w)=B，从而00δˆ(q,wc)=B。0若c=1，则当
9、w中含偶数个1时由于DFA不接受w，故δˆ(q,w)=A，从而0δˆ(q,wc)=B；当w中含奇数个1时由于DFA接受w，故δˆ(q,w)=B，从而00δˆ(q,wc)=A。0总之，当wc中含偶数个1时DFA不接受wc，当wc中含奇数个1时DFA接受wc。命题得证。习题2.2.111)将DFA改写成转移图形式：100,100A1BC2）观察上图，知其接受的语言应为L＝{w∈{0,1}*:w不含子串00}.3)用数学归纳法证明2）中的断言，过程与前题类似。习题2.3.201→{p}{q,s}{q}*{q,s}{r}{p,q,r}*{
10、q}{r}{q,r}{r}{s}{p}*{q,r}{r,s}{p,q,r}*{s}∅{p}*{r,s}{s}{p}*{p,q,r}{q,r,s}{p,q,r}*{q,r,s}{r,s}{p,q,r}∅∅∅习题2.3.31)将NFA转化为DFA：01→{p}{p,q}{p}{p,q}{p,q,r,s}{p,t}*{p,q,r,s}{p,q,r,s}{p,t}*{p,t}{p,q}{p}2)将转移表改写为转移图：11001{p,t}{p}{p,q}01{p,q,r,s}0观察此图，知其接受的语言应为L＝{w∈{0,1}*:w以00或0
11、1结尾}.习题2.3.4a）∑00∑∑11……∑99c)01011111111习题2.4.1a,ba)abcdacd0,1b)010111101a,b,cc)abbcca习题2.5.1a)ECLOSE(p)={p},ECLOSE(q)={q,p},ECLOSE(r)={r,q,p}b)自动机接受的长度为1的串有c；自动机接受的长度为2的串有ac,bb,bc,ca,cb,cc；自动机接受的长度为3的串有aac,abb,abc,aca,acb,acc,bab,bac,bba,bbb,bbc,bca,bcb,bcc.abcc)→{p}{
12、p}{p,q}{p,q,r}{q}{p,q}{p,q,r}{p,q,r}*{r}{p,q,r}{p,q,r}{p,q,r}{p,q}{p,q}{p,q,r}{p,q,r}*{p,q,r}{p,q,r}{p,q,r}{p,q,r}习题2.5.3a)abcεε10b)εεεε001c)10,10,10,1εεε,0,110,1εε,0,1ε,0,11第三章习题解答习题3.1.1a)(a+b+c)*(a+b)(a+b+c)*（或的答案）(a+b+c)*(a(a+b+c)*b+b(a+b+c)*a)(a+b+c)*9b)(0+1)*1(0
13、+1)c)((01+0)*+(10+0)*)+(10+0)*11(01+0)*习题3.1.2a)(01+0011)*b)1*(01*01*01*01*0)*1*习题3.1.4a)不连续出现1的串的集合b)含子串000的串的集合c)不连续出现1的串的集合习题3.1.5{ε}习题3.2.1DFA的转移图为1000q1q31q21d)1*0(11*0)*0(0+1(11*0)*0)*e)(1+01)*00(0+10)*习题3.2.3将DFA写成转移图形式，然后改成标准形式，以此为基础逐个消去中间结点：sr110εp0011ε0qs10ε
14、p0+10*11ε0qs(0+10*1)110εp(0+10*1)0ε1+0((0+10*1)1)*(0+10*1)0εpε(1+0((0+10*1)1)*(0+10*1)0)*故DFA相应的正则表达式为(1+0((0+10*1)1)*(0+10*
