自动机习题中文解答全.doc

自动机习题中文解答全.doc

《自动机习题中文解答全.doc》由会员分享，可在线阅读，更多相关《自动机习题中文解答全.doc（21页珍藏版）》请在冰点文库上搜索。

第二章习题解答

习题2.2.4

0

1

1

0

1

0

a）

0

1

1

0

1

0

0,1

b）

0

1

0

1

0

1

0,1

c）

习题2.2.9

a）对|w|作归纳法。

当|w|=1时w为一字符，由题设已成立。

设，

则对任一字母a，有　

b）对k作归纳法。

k=1时，由题设命题已成立。

设xkÎL（A），即。

于是　，即xk＋1ÎL（A），证毕。

习题2.2.10

1

0

A

B

1

0

1）将DFA改写成转移图形式：

2）观察上图，知其接受的语言应为

　　　　　　L＝{wÎ{0,1}*:

w含奇数个1}.

3）用数学归纳法证明2）中的断言：

当|w|=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，故，从而；当w中含奇数个1时由于DFA接受w，故，从而。

　　若c=1，则当w中含偶数个1时由于DFA不接受w，故，从而；当w中含奇数个1时由于DFA接受w，故，从而。

总之，当wc中含偶数个1时DFA不接受wc，当wc中含奇数个1时DFA接受wc。

命题得证。

习题2.2.11

1）将DFA改写成转移图形式：

0

1

A

B

1

0

C

0

0,1

2）观察上图，知其接受的语言应为

　　　　　　L＝{wÎ{0,1}*:

w不含子串00}.

3）用数学归纳法证明2）中的断言，过程与前题类似。

习题2.3.2

01

®{p}{q,s}{q}

*{q,s}{r}{p,q,r}

*{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.3

1）将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）将转移表改写为转移图：

0

0

1

{p,q}

1

0

1

{p}

{p,q,r,s}

{p,t}

1

0

观察此图，知其接受的语言应为

　　　　　　L＝{wÎ{0,1}*:

w以00或01结尾}.

习题2.3.4

0

å

å

0

1

9

å

å

1

9

……

a）

1

1

1

1

1

1

1

1

1

0

0

c）

c

b

a

a

d

c

d

a,b

习题2.4.1

a）

0

1

0

1

1

1

1

0

1

0,1

b）

a

b

b

c

c

a,b,c

a

c）

习题2.5.1

a）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.

abc

®{p}{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}

c）

习题2.5.3

a

e

e

b

c

a）

1

e

0

e

0

1

0

e

b）

e

c）

0,1

0,1

1

1

e,0,1

e,0,1

0,1

1

e,0,1

e

0,1

e

e

第三章习题解答

习题3.1.1

a）（a+b+c）*（a+b）（a+b+c）*（或的答案）（a+b+c）*（a（a+b+c）*b+b（a+b+c）*a）（a+b+c）*

b）（0+1）*1（0+1）9

c）（（01+0）*+（10+0）*）+（10+0）*11（01+0）*

习题3.1.2

a）（01+0011）*

b）1*（01*01*01*01*0）*1*

习题3.1.4

a）不连续出现1的串的集合

b）含子串000的串的集合

c）不连续出现1的串的集合

习题3.1.5{e}

习题3.2.1DFA的转移图为

0

1

0

1

0

1

q1

q3

q2

d）1*0（11*0）*0（0+1（11*0）*0）*

e）（1+01）*00（0+10）*

习题3.2.3将DFA写成转移图形式，然后改成标准形式，以此为基础逐个消去中间结点：

1

0

0

0

1

1

1

0

e

e

p

s

r

q

1

0

0

0+10*1

1

e

e

p

s

q

1

0

（0+10*1）1

e

e

p

s

（0+10*1）0

1+0（（0+10*1）1）*（0+10*1）0

e

e

p

（1+0（（0+10*1）1）*（0+10*1）0）*

故DFA相应的正则表达式为　（1+0（（0+10*1）1）*（0+10*1）0）*.

（注意：

消中间结点的顺序不同，所得正则表达式就可能不一样）

0

1

e

习题3.2.4

a）

0

e

e

1

0

1

b）

0,1

e

0

1

c）

习题3.2.5

0

1

a）

0,1

0

1

b）

0,1

0

1

c）

习题3.2.补充题　

a

a

a

a

b

e

b

e

e

（a）（ab）*（ba）*Èaa*

（b）（（abÈaab）*a*）*

a

>

a

a

b

b

e

e

e

e

（c）（baÈb）*È（bbÈa）*

e

>

a

b

b

a

b

b

e

e

e

b

>

a

a

e

b

a,b

e

a

（d）a*（abÈbaÈe）b*

（e）（（aÈb）*（aÈc）*）*

>

e

a,b

e

a,c

e

（f）（（ab）*È（bc）*）ab

e

b

a

a

a

b

b

>

习题3.4.1实际上就是要求验证等式两端的集合相等：

a）－e）.证明略。

f）先证R*Í（R*）*。

因为　RÍR*,所以根据星号运算的定义易知R*Í（R*）*。

再证（R*）*ÍR*。

　任取wÎ（R*）*,　由星号定义存在wkÎR*,k=1,2,…,n,使得　w=w1w2….wn。

对于每个wkÎR*，由星号定义存在wkjÎR,j=1,2,…,nk,使得

wk=wk1wk2….wknk,k=1,2,…,n.

于是w=w11w12….w1n1w21w22….w2n2….wn1wn2….wnnn，即w可以表示成若干个R的串的连接，由星号定义有wÎR*，故（R*）*ÍR*。

综上所述，有（R*）*=R*。

h）显然RÈSÍR*S*，故（RÈS）*Í（R*S*）*。

反过来，对于任意的wÎ（R*S*）*,　由星号定义存在wkÎR*S*,k=1,2,…,n,使得　w=w1w2….wn。

设wk＝rksk，其中rkÎR*，skÎS*,k=1,2,…,n。

这样，每个rk可以表示成若干个R的串的连接，每个sk可以表示成若干个R的串的连接，从而w可以表示成若干个RÈS的串的连接，这说明（R*S*）*Í（RÈS）*。

所以　（R*S*）*=（RÈS）*。

习题3.4.2

a）不成立。

请看以下反例：

当R={1},S={0}时，串1010出现在等式左端的集合中，但不出现在等式右端集合中。

d）不成立。

请看以下反例：

当R={1},S={0}时，串e出现在等式右端的集合中，但不出现在等式左端集合中。

习题3.4.3　　（0+1）*1（0+1）（e+0+!

）

第四章习题解答

习题4.1.1

a）记此语言为L。

反设L是正则的，则泵引理成立。

对于泵引理中相应于L的正整数N,取w=0N1N,由于

w=xyz,|xy|<=N,y≠e且xyiz在L中，i=0,1,2,….

故x=0k,y=0k’,k’>0.因此xy0z=0N－k’1N不在L中,矛盾。

b）记此语言为L。

反设L是正则的，则泵引理成立。

对于泵引理中相应于L的正整数N,取w=（N）N,由于

w=xyz,|xy|<=N,y≠e且xyiz在L中，i=0,1,2,….

故x=0k,y=0k’,k’>0.因此xy0z=（N－k’）N不在L中,矛盾。

c）记此语言为L。

反设L是正则的，则泵引理成立。

对于泵引理中相应于L的正整数N,取w=0N10N,由于

w=xyz,|xy|<=N,y≠e且xyiz在L中，i=0,1,2,….

故x=0k,y=0k’,k’>0.因此xy0z=0N－k’10N不在L中,矛盾。

d）记此语言为L。

反设L是正则的，则泵引理成立。

对于泵引理中相应于L的正整数N,取w=0N12N,由于

w=xyz,|xy|<=N,y≠e且xyiz在L中，i=0,1,2,….

故x=0k,y=0k’,k’>0.因此xy0z=0N－k’12N不在L中,矛盾。

e）记此语言为L。

反设L是正则的，则泵引理成立。

对于泵引理中相应于L的正整数N,取w=0N1N,由于

w=xyz,|xy|<=N,y≠e且xyiz在L中，i=0,1,2,….

故x=0k,y=0k’,k’>0.因此xy0z=0N－k’1N不在L中,矛盾。

f）记此语言为L。

反设L是正则的，则泵引理成立。

对于泵引理中相应于L的正整数N,取w=0N12N,由于

w=xyz,|xy|<=N,y≠e且xyiz在L中，i=0,1,2,….

故x=0k,y=0k’,k’>0.因此xy0z=0N－k’12N不在L中,矛盾。

习题4.1.2

a）记此语言为L。

反设L是正则的，则泵引理成立。

对于泵引理中相应于L的正整数N,取w=0N´N,则

w=xyz,|xy|<=N,y≠e且xyiz在L中，i=0,1,2,….

设xz=0p,y=0q,则　xyiz=0p+iqÎL,i=0,1,2,…

所以　p+iq=n2i,i=1,2,….

于是q=n2i+1-n2i≥（ni+1）2-n2i=2ni+1.

令i趋于无穷大，则由以上不等式可得q≥+∞，矛盾。

b）类似a）可证。

c）记此语言为L。

反设L是正则的，则泵引理成立。

对于泵引理中相应于L的正整数N,取w=0M,其中M＝2N，则

w=xyz,|xy|<=N,y≠e且xyiz在L中，i=0,1,2,….

设xz=0p,y=0q,则　xyiz=0p+iqÎL,i=0,1,2,…

所以　p+iq=2Ni,i=1,2,….

于是（p+（i+1）q）/（p+iq）≥2,

令i趋于无穷大，则由以上不等式可得1≥2，矛盾。

习题4.1.4

a）长度不够，即无法找到长度符合要求的w。

b）长度不够，即无法找到长度符合要求的w。

c）无法找到自然数k使xykzÏL。

习题4.2.1

a）h（0120）=aabbaa

b）h（21120）=baababbaa

c）L（a（ab）*ba）

d）L（a+abba）

e）h-1（L）={022,102,110}

f）h-1（L）=L（1*02*）

习题4.2.2

a）若L是任一正则语言，设接受L的DFA为A＝（Q,Σ,δ,q0,F）

，据此可以构造另一台DFA　B＝（Q,Σ,δ,q0,F1），其中前四项与A相同，而取

F1＝{qÎF:

若则对于w的任一真前缀w1有}，

则B接受的语言就是min（L），故min（L）是正则的。

b）若L是任一正则语言，设接受L的DFA为A＝（Q,Σ,δ,q0,F）

，据此可以构造另一台DFA　B＝（Q,Σ,δ,q0,F1），其中前四项与A相同，而取F1=F－F2,其中

F2＝{qÎF:

存在w使且有w的真前缀w1使}，

则B接受的语言就是max（L），故max（L）是正则的。

c）若L是任一正则语言，设接受L的DFA为A＝（Q,Σ,δ,q0,F）

，据此可以构造另一台DFA　B＝（Q,Σ,δ,q0,F1），其中前四项与A相同，而取

F1＝{qÎF:

存在w使且有w的前缀w1使}，

则B接受的语言就是init（L），故init（L）是正则的。

习题4.4.1

x

x

x

B

C

E

D

F

H

G

G

A

B

C

D

E

F

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

B

C

E

D

F

H

G

G

A

B

C

D

E

F

x

x

x

x

x

x

x

x

x

x

x

a）

可到D：

CE|H

 不能到D：

ABFG

故去掉不可达状态H后，状态的等价类共有4个：

{A,G},{B,F},{C,E},{D}，从而最小DFA为

0

0

0

0

{A,G}

1

1

1

1

{C,E}

{B,F}

D

习题4.4.2

x

x

x

x

G

C

D

E

F

x

x

x

x

x

x

x

x

x

x

x

x

H

x

x

x

x

x

x

x

x

B

C

E

D

F

H

G

A

B

x

x

x

I

x

x

x

x

G

C

D

E

F

x

x

x

x

x

x

x

x

H

x

x

x

B

C

E

D

F

H

G

A

B

x

x

x

I

a）

可到CFI：

BEH

 不能到CFI：

ADG

1

0

{A,D,G}

{B,E,H}

{C,F,I}

0

0,1

1

由于没有不可达状态，故状态的等价类共有3个：

{A,D,G},{C,F,I},{B,E,H}，从而最小DFA为

第五章习题解答

习题5.1.1

a）用归纳的办法定义L：

（1）基础：

01ÎL；

（2）归纳：

若SÎL，则0S1ÎL.

除此之外L没有别的串了。

这两条可用产生式S®01,S®0S1生成，从而生成L的CFG为

G=（V,T,P,S），其中V＝{S},T={0,1},P={S®01,S®0S1}.

b）L可以分解为四部分：

{aibjck|ij}È{aibjck|jk},

生成L的CFG为G=（V,T,P,S），其中V＝{S,S1,C1,S2,A,S3,S4},T={a,b},

P={S®S1C1|S2C1|AS3|AS4,

C1®cC1|e,A®aA|e,

S1®aS1b|S1b|b,S2®aS2b|aS2|a,

S3®bS3c|S3c|c,S4®bS4c|bS4|b.

}

d）生成L的CFG为G=（V,T,P,S），其中V＝{S},T={0,1},

P={S®001S|00S1|0S01|S001|010S|01S0|0S10|S010|100S|10S0|1S00|S100}

习题5.1.2

a）一个最左推导为

SÞA1BÞ0A1BÞ00A1BÞ001BÞ0010BÞ00101BÞ00101，

一个最右推导为

SÞA1BÞA10BÞA101BÞA101Þ0A101Þ00A101Þ00101。

b）一个最左推导为

SÞA1BÞ1BÞ10BÞ100BÞ1001BÞ1001，

一个最右推导为

SÞA1BÞA1BÞA10BÞA100BÞA1001BÞA1001Þ1001。

c）一个最左推导为

SÞA1BÞ0A1BÞ00A1BÞ000A1BÞ0001BÞ00011BÞ00011，

一个最右推导为

SÞA1BÞA11BÞ0A11Þ00A11Þ000A11Þ00011.

习题5.1.3见教案（第五章第一节最后一个例子）

习题5.2.1a）b）c）

S

A

1

B

1

B

e

0

A

0

A

0

A

e

0

A

0

A

S

A

1

B

0

B

1

B

e

e

S

A

1

B

0

B

0

B

1

B

e

e

习题5.2.2对m作归纳法。

m=1时，有根节点，以及至少n个叶子节点，故语法分析树至少有1+n个节点；设推导m步时命题成立。

当推导需m+1步时，前m步推导产生的语法分析树的节点至少有m+n个，由于还需一步推导，故还有一个叶子节点为变元，此变元经最后一步推导后至少增加一个节点，即语法分析树的节点至少有m+n+1个。

习题5.3.2生成L的CFG为G=（V,T,P,S），其中V＝{S},T={0,1},

P={S®SS|（S）|[S]|e}.

习题5.3.5对应的规则（产生式）为：

1）COURSES®COURSE1,COURSE1®COURSE·COURSE1|COURSE,

2）COURSE®CNAME·PROF·STUDENT1·TA1,

STUDENT1®STUDENT·STUDENT1|STUDENT,TA1®TA|e,

3）CNME®#PCDATA,

4）PROF®#PCDATA,

5）STUDENT®#PCDATA,

6）TA®#PCDATA.

习题5.4.1

a）以下两棵语法分析树都能得到串aab：

e

S

a

b

S

S

a

S

e

a

S

S

S

a

b

S

e

e

b）以上两棵语法分析树分别对应的最左推导为：

SÞaSÞaaSbSÞaabSÞaab,

以及

SÞaSbSÞaaSbSÞaabSÞaab.

c）以上两