形式語(yǔ)言與自動(dòng)機(jī)理論-第三章參考答案

第三章作業(yè)答案

1.已知DFAMl與M2如圖3—18所示。(xxxx02282068)

(1)請(qǐng)分別給出它們?cè)谔幚碜址?011001的過(guò)程中經(jīng)過(guò)的狀

態(tài)序列。

(2)請(qǐng)給出它們的形式描述。

圖3—18兩個(gè)不同的DFA

解答：(1)M1在處理1011001的過(guò)程中經(jīng)過(guò)的狀態(tài)序列為

q0q3qlq3q2q3qlq3;

M2在處理1011001的過(guò)程中經(jīng)過(guò)的狀態(tài)序列為

q0q2q3qlq3q2q3ql;

(2)考慮到用形式語(yǔ)言表示，用自然語(yǔ)言似乎不是那么容易，所以

用圖上作業(yè)法把它們用正則表達(dá)式來(lái)描述:

Ml:[01+(00+1)(11+0)][11+(10+0)(11+0)]*

M2:(01+1+000){(01)*+[(001+11)(01+1+000)]*}

*1**A**T*

*T**T**T?*T**7**T**T**Tw*T**T**T*

*1**1**1**1**1**4*^^*1**1**A**X*

*T**T^*TSZ7^>T*yT*

2.構(gòu)造下列語(yǔ)言的DFA(xx02282085)

(1){0,1}*

(2){0,1}+

S——KOA-(^>^C1

(3){x|x{0,1}+且x中不含00的串}

(設(shè)置一個(gè)陷阱狀態(tài)，一旦發(fā)現(xiàn)有00的子串，就進(jìn)入陷阱狀態(tài))

(4){x|x{0,1}*且x中不含00的串}

(可接受空字符串，所以初始狀態(tài)也是接受狀態(tài))

(5){x|x{0,1}+且x中含形如10110的子串}

(6){x|x{0,1}+且x中不含形如形110的子串}

(設(shè)置一個(gè)陷阱狀態(tài)，一旦發(fā)現(xiàn)有00的子串，就進(jìn)入陷阱狀態(tài))

(7){x|x{0,1}+且當(dāng)把x看成二進(jìn)制時(shí)，x模5和3同余，要求當(dāng)

x為0時(shí),|x|=1,且x0時(shí)，x的首字符為1}

1.以0開(kāi)頭的串不被接受，故設(shè)置陷阱狀態(tài)，當(dāng)DFA在啟動(dòng)狀態(tài)讀

入的符號(hào)為0,則進(jìn)入陷阱狀態(tài)

(10){x|x{0,1}+且XXX至少含有兩個(gè)1}

(11){x|x{0,1}+且如果x以1結(jié)尾，則它的XX為偶數(shù)；如果x以

0結(jié)尾，則它的xx為奇數(shù)}

可將{0,1}+的字符串分為4個(gè)等價(jià)類(lèi)。

q0：［］的等價(jià)類(lèi)，對(duì)應(yīng)的狀態(tài)為終止?fàn)顟B(tài)

ql:x的xx為奇且以0結(jié)尾的等價(jià)類(lèi)

q2：x的xx為奇且以1結(jié)尾的等價(jià)類(lèi)

q3：x的xx為偶且以0結(jié)尾的等價(jià)類(lèi)

q4:x的xx為偶且以1結(jié)尾的等價(jià)類(lèi)

（12）{x|x是十進(jìn)制非負(fù)數(shù)}

0,1.2,3,4,

5,6,7,8,9

(13)

s-KDO

(14)

>lz

^T>^Tx^T><i%<T>x7^<T>xi><T%^T>^T>

*1^.〉vl*」,.〉st*7/vt*7/.〉*Tzvj^X****XK*X**X.：?*A**^Z.〉vtx.〉st*7/

^T><T^^T>^T>^S*7^^T**T*

3(1)(xx02282061)

0

={0,1}

Set(q0)={x|x*}

(2)

={0,1}

Set(q0)=

Set(ql)={x|x+)

(3)

={0,1}

Set(qO)=

Set(ql)={x|x+并且x中不含形如00的子串}

Set(q2)={x|x+并且x中不含形如00的子串}

(4)

={0,1}

Set(q0)={x|x*并且x中不含形如00的子串}

Set(ql)={x|x*并且x中不含形如00的子串}

⑸

={0,1}

Set(q0)={x|x*,并且x{0}*或者x中含形如100的子串}

Set(ql)={x|x*,并且x中含形如1的子串}

Set(q2)={x|x*，并且x中含形如10的子串}

Set(q3)={x|x*,并且x中含形如101的子串}

Set(q4)={x|x*,并且x中含形如1011的子串}

Set(q5)={x|x*,并且x中含形如10110的子串}

(6)

={0,1}

Set(q0)={}

Set(ql)={xx{0+}}

Set(q2)={xx*,并且xxx不含形如10110的子串而且XXX

含有1}

Set(q3)={xX*,并且XXX不含形如10110的子串而且XXX

含有1}

⑺

={o,1}

Set(qs)={}

Set(qe)={0}

Set(ql)={x|x+,并且把x看成二進(jìn)制數(shù)時(shí),x%5=1}

Set(q2)={x|x+,并且把x看成二進(jìn)制數(shù)時(shí),x%5=2}

Set(q3)={x|x+,并且把x看成二進(jìn)制數(shù)時(shí),x%5=3}

Set(q4)={x|x+,并且把x看成二進(jìn)制數(shù)時(shí)，x%5=4}

Set(q0)={x|x+,并且把x看成二進(jìn)制數(shù)時(shí)，x%5二0并且x

不為0}

(8)

M={Q,,,qO,F)

Q={q0,ql,q2,—qlO}

={0,1}

當(dāng)0<=i<=8時(shí)侯，

(qi,0)=(qi,l)=q(i+1)

(q9,l)=qlO

(q10,0)=(q10,l)=ql0

F={q10}

Set(q0)={}

Set(ql)={0,1}

Set(q2)={x|x+,并且|x|=2}

Set(q3)={x|X+,并且|XI二3}

Set(q4)={x|x+,并且|x|=4}

Set(q5)={x|x+,并且|x|二5}

Set(q6)={x|x+,并且|x1=6}

Set(q7)={x|x+,并且|x|=7}

Set(q8)=(x|X+,并且|X|=8}

Set(q9)={xx+,并且|x|=9}

Set(qlO)={x|x+,并且x的第十個(gè)字符是1}

(9)M={Q,,,qO,F}

Q={qO,ql,Q2}

二{0,1}

(q0,0)=ql

(q1,0)=ql

(q1,1)=q2

(q2,1)二q2

(q2,0)=ql

F={q2}

Set(Q0)-{}

Set(ql)={x|x+,并且x以0開(kāi)頭以0結(jié)尾}

Set(q2)={x|x+,并且x以0開(kāi)頭以1結(jié)尾}

(10)M={Q,,,qO,F}

Q={qO,ql,q2}

={o,1}

(q0,0)=q0

(q0,l)=ql

(q1,0)=ql

(q1,1)=q2

(q2,1)=q2

(q2,0)二q2

F={q2}

Set(q0)={0}*

Set(ql)={x|x+,并且xxx只有一個(gè)1}

Set(q2)={x|x+,并且x至少有倆個(gè)1}

(11)M={Q,,,qO,F}

Q={q0,ql,q2,q3,q4}

={0,1}

(Q0,0)=ql

(Q0,D=q4

(q1,0)=q3

(q1,D=q2

(q2,1)=q4

(q2,0)=ql

(q3,0)=ql

(q3,1)=q4

(q4,1)=q2

(q4,0)=q3

F={q0,q1,q2}

Set(qO)=(}

Set(ql)={xx+,以0結(jié)尾，xx為奇數(shù)｝

Set(q2)={xX+,以1結(jié)尾，XX為偶數(shù)｝

Set(q3)=(xx+,以0結(jié)尾，xx為偶數(shù)｝

Set(q4)={xx+,以1結(jié)尾，xx為奇數(shù)｝

(12)

M={Q,,,qO,F)

Q={qO,ql,q2,q3,q4}

={.,0,1,2,—,9}

F={ql,q2,q4}

(q0,0)=ql

(q0,l|2|3|4|5|6|7|8|9)=q2

(q1,.)=q2

(q2,0|l|2|3|4|5|6|7|8|9)=q2

(Q2,.)—q3

(q3,0|l|2|3|4|5|6|7|8|9)=q4

(q4,0|l|2|3|4|5|6|7|8|9)=q4

Set(q0)={}

Set(ql)={0}

Set(q2)={十進(jìn)制正整數(shù)}

Set(q3)={十進(jìn)制非負(fù)整數(shù)后面接個(gè)小數(shù)點(diǎn).}

Set(q4)=｛十進(jìn)制正小數(shù)｝

(13)

------?④(@)

Set(qO)={}

Set(qO)=

(14)

—

Set(qO)={}

*T**T**Y**7**T?xr**T^*T**7**T**T*#r^*r?*1**T**￡**TX*T?*￡**A*#T%*7￡*?*Tx4、

*)!**X**Aj**T**LT**47**T**L|*r*L7**X**T**X?>L*%^**T**X**^*

4在例3-6xx,狀態(tài)采用的形式，它比較清楚地表達(dá)出該狀態(tài)所對(duì)

應(yīng)的記憶內(nèi)容，給我們解決此問(wèn)題帶來(lái)了很大的方便，我們是否

可以直接用代替呢？如果能，為什么？如果不能，又是為什么？

從此問(wèn)題的討論，你能總結(jié)出什么來(lái)？(xxxx02282084)

答：我認(rèn)為能夠直接用代替，因?yàn)樵诶?-6xx,只是一種新的表示方

法，用來(lái)表示狀態(tài)存儲(chǔ)的字符，這樣就省去了在xx逐一給出每

一個(gè)具體的輸入字符和狀態(tài)的定義。它的作用在于使FAxx狀態(tài)

定義更加簡(jiǎn)潔c

得到結(jié)論：在今后描述FA時(shí)，應(yīng)該根據(jù)具體的情況，使用適

當(dāng)?shù)姆椒ā?/p>

si*7/st*KJX7/vl*vj-*vjxst*vl*KJ-*/*1**t*?>KJX7/V*Z.〉vl*4/K*Xvt*vl*vjx7/KJX

^1%^1%*T><1%<1%^T*^1%

>1^>1^^1^

*T**T**r**7**T**T**i**7**T**T*

5.試區(qū)別FA中的陷阱狀態(tài)和不可達(dá)狀態(tài)。（xx賢培02282047）

解：（D陷阱狀態(tài)（課本97頁(yè)）：指在其它狀態(tài)下發(fā)現(xiàn)輸入串不可能

是該FA所識(shí)別的句子時(shí)所進(jìn)入的狀態(tài)。FA一旦進(jìn)入該狀態(tài),

就無(wú)法離開(kāi)，并在此狀態(tài)下，讀完輸入串中剩余的字符。

⑵不可達(dá)狀態(tài)（課本108頁(yè)）：指從FA的開(kāi)始狀態(tài)出發(fā)，不可能到

達(dá)的狀態(tài)。就FA的狀態(tài)轉(zhuǎn)移圖來(lái)說(shuō)，就是不存在從開(kāi)始狀態(tài)

對(duì)應(yīng)的頂點(diǎn)出發(fā)，到達(dá)該狀態(tài)對(duì)應(yīng)頂點(diǎn)的路徑。

⑶從兩者的定義可見(jiàn)：相對(duì)于不可達(dá)狀態(tài)來(lái)說(shuō)，陷阱狀態(tài)是可達(dá)的。

但是，它們都是狀態(tài)轉(zhuǎn)移圖中的非正常狀態(tài)。如果從狀態(tài)轉(zhuǎn)

移圖中的狀態(tài)引一條弧到不可達(dá)狀態(tài)，同時(shí)不可達(dá)狀態(tài)所有

的移動(dòng)都是到自身。這樣，不可達(dá)狀態(tài)就變成了陷阱狀態(tài)。

six*lz*L*%￡z*JZ*Xz*L*SZZ^Lz*1*slz?￡zx￡z

4、*VS,卜XjX，,、/、，「4、<>>4、/卜*|X,卜<1>/卜*|X,卜<J、XjX.I、X|>,卜<|>X|X<j>4、,卜Z|>X|S/卜*|X,卜<i>*1S,'4、,卜<1>X|X<1>，卜xj、X|S,「X|>,卜4、q、/、''q、Xj>

sixKIXsixxix^3xvXxS￡X

<iX<T>^T>

注：此題目有問(wèn)題，可以將題設(shè)改為：xxxO和1個(gè)數(shù)相等且交替出

現(xiàn)

6.證明：題目有不嚴(yán)密之處，圖xx給出EFA與題目xx的語(yǔ)言L(M)

二{x|xx{0,1}+且xxxO的個(gè)數(shù)和1的個(gè)數(shù)相等}不完全對(duì)應(yīng),首

先圖xx的DFA可接受空字符串，而L(M)不接受，其次，對(duì)于

有些句子，例如1100,L(M)可以接受，但DFA不接受

(1)根據(jù)圖中的DFA可看出，右下角的狀態(tài)為陷阱狀態(tài)，所

以去除陷阱狀態(tài)

(2)由DFA可構(gòu)造出與其對(duì)應(yīng)的右線性文法：(xx02282083)

S—0A

Af1S|1

STTB

8-()S|0

將IS,1代入Sf0A；0S,0代入SfIB得

Sf01S|01

Sf105|10

由此可以看出該文法接受的語(yǔ)言為L(zhǎng)={(10|01)*},顯然01或10

分別是作為整體出現(xiàn)的，所以L(M)xxO和1的個(gè)數(shù)相等。

VX

*1**7**1^^T>*T**7**1*^7**y**7**7^*7*

*4*

ZTSZTXZT^Zl>ZjSZT^*jS?TX*?>Z7XZTNZTS#TXZTSZTXZT*ZTS

7.設(shè)DFAM=,證明：對(duì)于

注：采用歸納證明的思路

證明：(周期律02282067)

首先對(duì)y歸納，對(duì)任意x來(lái)說(shuō)，|y|二。時(shí)，即y二

根據(jù)DFA定義，故原式成立。

當(dāng)|y|二n時(shí)，假設(shè)原式成立，故當(dāng)|y|=n+l時(shí)，

不妨設(shè)y=wa,|w|=n,|a|=1

根據(jù)DFA定義，故

原式成立，

同理可證，對(duì)任意的y來(lái)說(shuō)，結(jié)論也是成立的。

綜上所述，原式得證

Klx、］,

zT^xr*ztsyr*zfxz?^*TvzfxzfxyTx^TszjsztszTxzj^ztsz?**Txzfxz%ZTSzjsztsy1*xrszy^zT^*tsz?*ZTXzTszfx>T*Zg^

KI>KI>?,

8.證明：對(duì)于任意的DFAM1=(Q,2,6,q0,Fl)存在DFA

M2=(Q,S,8,q0,F2),(xx02282075)

使得L(M2)=2*—L(Ml)o

證明：(1)構(gòu)造M2。

設(shè)DFAM1=(Q,S,8,q0,Fl)取DFAM2=(Q,2,8,q0,Q—Fl)

(2)證明L(M2)=2*—L(Ml)

對(duì)任意xX*

xL(M2)=2*—L(Ml)8(q,x)Q—Fl5(q,x)Q并且3

(q,x)FlxE*并且xL(Ml)xE*—L(Ml)

*.1**.1**1*\卜*A**4**>L*4,■],*L*■],*X*KL*.上

*T**T*^T**T**r**T?*T**r**T**T**T^*T**T**T**r**T**T**T*

*1>*X**1**1**4**L**J**1*%1**4**!*^^*1**1**X*

*T**T*>T**T**T**T*>T^

9.對(duì)于任意的DFAMl二(QI,￡,31,q01,Fl),請(qǐng)構(gòu)造DFA

M1=(Q2,L,52,q02,F2),使得L(M1)=L(M2)T。其中

L(M)T={x|xTeL(M)}(xx02282072)

(1)構(gòu)造E-NFAM使得L(M)=L(M1)取￡-NFAM=(Q,E,6,

q0,{qOl})其中：

1)Q=QIU{q0},qOQI

2)對(duì)于q,p￡Ql,a￡X,如果81(q,a)=p,q￡6(p,a)

3)6(qO,￡)二Fl

(2)證明：L(M)=L(M1)T

對(duì)x=a2…amL(M)

q2…am卜qfa2…am卜a1q2…am卜a2q2…

am卜???卜42…qm-lam

ka2…a:nqOl

其中qf￡6(qO,￡),qle6(qf,al),q2e8(ql,

a2),…qOl￡5(qm-1,am)并且qfWFl

則51(qOl,am)=qm-1,51(qm-1,am-l)=qm-2,51(q2,

a2)=ql61(ql,al)二qf

因止匕qOlamamT…al卜amqmTam-l…al卜am

am-1…ql|-amamT…a2ql

pamamT…alqf

因此amamT???al￡L(Ml)即xT^L(Ml)

同理可證對(duì)于x=a2…am^L(Ml)xT=am

am-l??,alEL(Ml)

以田二口皿丹得證

(3)將￡-NFAM確定化

首先構(gòu)造與￡-NFAM=(Q,S,6,qO,{qOl})等價(jià)的NFA

M3=(Q,￡,32,qO,{qOl})

其中對(duì)于(q,a)62(q,a)=6(q,a)

然后按照以前學(xué)過(guò)的方法構(gòu)造與NFAM3=(Q,E,52,qO,(qOl})

等價(jià)的DFA

M1=(Q1,L,61,[qO],Fl)其中：Q1=2QFl={qOl}

6l([ql,q2,???,qn],a)=[pl,p2,—,pn]當(dāng)且僅當(dāng)

62({ql,q2，…,qn},a)={pl,p2,?-?,pn}

*A**￡**1**￡**￡**A**x**.1**x**1**￡**￡**X**X**.1**￡?*A*

*1**T*??J、*g**7**7**T**Tw*7**Tw*T**T*4■*7**T**7**T**T*"■*7**T**r**7**T**r**T**T**T**T**r**T**7**7**T**7*??*7**T**Tw*T**T**7**T*

*1*7.*?**1**1**i**1*X1*Kix*￡*

■一■..*T**>*■.■■>■.■■K1J■***?￡**■..*T*■K.J■X■[■*■*■.■*i*■?■*?*■.■■[■■..*T*■-

注：此題(10題)xx^XX所做完全一樣?。?/p>

10、構(gòu)造識(shí)別下列語(yǔ)言的NFA(xx02282091)

(1){1,￡{0』}’.目時(shí)不含形勿100的子串}

1

___r--■-

,■

1

(2){x|xG{O,l}h且x中含形如10110的子串}

―

0.?_,°

一7~I4

￡

(1.1

⑶{小€{0,1}+.目時(shí)不含形如10110的子串}

!——O-^->?---------------H——

0.I°

0.I

(4){AXG{0,1}+和地勺倒數(shù)第10個(gè)字符是1,且以01結(jié)尾}

0.I

(5){x|xe{O,l}+且似0開(kāi)頭以1結(jié)尾}

(6){x|xe{0Jf至少含有兩個(gè)1}

o.1

0.I

(7){]k￡{0,1}'且如果,似1結(jié)尾，則它的長(zhǎng)度為偶數(shù);

如果以0結(jié)尾，則它的長(zhǎng)度為奇數(shù)}

(8){xX￡{0』}+FLxft勺首字符和尾字符相等}

0.I

(9){xcox'x,<yw{0」}'}

0.1

0.1

這是最基本的單元，其他的可以通過(guò)這個(gè)逐級(jí)構(gòu)造出來(lái)，以滿足

題目要求。

************************1],根據(jù)給定的NFA,構(gòu)造與之等價(jià)的DFA.

(xx02282090)

(1)NFAMl的狀態(tài)轉(zhuǎn)移函數(shù)如表3-9

狀態(tài)說(shuō)明狀態(tài)輸入字符

012

開(kāi)始狀態(tài)qo{qO,ql)fq0,q2){q0,q2|

ql{q3,qO)0{q2}

q20{q3,ql}{q2,ql}

終止?fàn)顟B(tài)q3{q3,q2}{q3}{q0}

解答:

狀態(tài)說(shuō)明狀態(tài)輸入字符

012

開(kāi)始狀態(tài)qo[qO,ql][qO,q2]lq0,q2]

[qO,ql][qO,ql,q3][q0,q2][q0,q2]

[qO,q2][qO,qlllqO,ql,q2,q3]IqO,ql,q2]

[qO,ql,q2][qO,ql,q3][qO,ql,q2,q3][qO,ql,q2]

終止?fàn)顟B(tài)[qO,ql,q3][q0,qhq2,q3][qO,q2,q3][qO,ql,q2]

終止?fàn)顟B(tài)[q0,q2,q3][q0,ql,q2,q3][qO,ql,q2,q3jIqO,q2|

終止?fàn)顟B(tài)[q0,ql,q2,q3]LqO,ql,q2,q3][q0,ql,q2,q3][q0,ql,q2]

■Ogi]0[qO,ql,q3][q(),g2,q引

q。。丁,J-◎

0%2/201

1,2./\0/y

r">2a，1oj1

7

rO1[q0,ql,q2,q3]

[qo,q2][q0，qi，q2]、7

1

圖3-9所示NFA等價(jià)的DFA

(2)NFAM2的狀態(tài)轉(zhuǎn)移函數(shù)如表3T0

狀態(tài)說(shuō)明狀態(tài)輸入字符

012

開(kāi)始狀態(tài)q0{ql，q3}{ql}{q0}

qi{q2}{qi,q2}{ql}

q2{q3,q2}(q0){q2}

終止?fàn)顟B(tài)q3{q。}{q3}

0

解答:

狀態(tài)說(shuō)明狀態(tài)輸入字符

012

開(kāi)始狀態(tài)q0[qhq3][qUIqOJ

[ql,q3][q2]Iq0,ql,q2]lql,q3]

[ql][q2][qLq2][qU

[q2]Iq2,q3][qO][q2]

[q0,ql,q2][ql,q2,q3][q0,ql,q2][q0,qhq2]

[qhq2][q2,q3]lq0,ql,q21Iql,q2]

終止?fàn)顟B(tài)[q2,q3][q2,q3][qO]Iq2,q3]

終止?fàn)顟B(tài)[ql,q2,q3][q2,q3]|q0,ql,q2]Iql,q2,q3]

[q0,ql,q2]

|q1,q3]廠12-

7^2IJ、、0[q3.ql.q2]

2

?

d眄。；QT

卬1°__-X2J2y[q2,q3]

i

圖3-10所示NFA等價(jià)的DFA

、]，*J**,L*■]，%A??[1**X**L*■].、〃*A*、]，■].*X*?],\>%L**1*■>*A**L*■]**J<*1**A**,L**X*、]*■]，■]，%!>%.L*、]**A*

*l?*T**T*

K|>K!Xx!xK￡>K￡>KI>K!>

zj^yj*zT?yt*xT^

12.證明對(duì)于任意的NFA,存在與之等價(jià)的NFA,該NFA最多只有

一個(gè)終止?fàn)顟B(tài)

(xx02282083)

證明：對(duì)于任意的NFAM=(Q,￡,6,q0,F),我們?nèi)绻軜?gòu)

造出一個(gè)只有一個(gè)終止?fàn)顟B(tài)的NFA,并且與之等價(jià)，即可證明上面的

定理

而對(duì)于任意的NFA存在下面兩種情況：

(1)終止?fàn)顟B(tài)只有一個(gè)

(2)終止?fàn)顟B(tài)有多個(gè)

要構(gòu)造這個(gè)等價(jià)的NFA,可以采用如下方法：

對(duì)(1)無(wú)需變化，該NFA即為滿足條件的NFA

對(duì)⑵可以在該NFA的狀態(tài)圖上添加一個(gè)新的終止?fàn)顟B(tài)，并將原

來(lái)的多個(gè)終止?fàn)顟B(tài)所連接的弧復(fù)制到該狀態(tài)上，此時(shí)這個(gè)終止?fàn)顟B(tài)為

新?tīng)顟B(tài)圖中唯一的終止?fàn)顟B(tài)，且這個(gè)新的NFA與原NFA等價(jià)，滿足

條件

我們總能構(gòu)造出這樣的NFA

因此對(duì)于任意的NFA,存在與之等價(jià)的NFA,該NFA最多只有一個(gè)

終止?fàn)顟B(tài)

*>1**1**￡**>1**1**￡**>1*

*1**T**T**T**T**T**T**7**T**7**T**T**7**T**T**T**r**T**7**T**T**7**T**v**T**T**T**T**T**7**T*

13.試給出一個(gè)構(gòu)造方法，對(duì)于任意的NFA，構(gòu)造NFA，使得

注：轉(zhuǎn)化成相應(yīng)的DFA進(jìn)行處理，然后可參考第8題的思路

證明：（周期律02282067）

首先構(gòu)造一個(gè)與NFA等價(jià)的DFA,根據(jù)定理3.1（P106）,

構(gòu)造其中

，〃，

=2°,居={[P”“2…P,"I{P]2…P”JG。，{PlPl…P,”}n片￥。},{P],p2...P力}qQ,。wZ

）（（

國(guó)（[%???%]，4=[p-Pm]<=>d{%..4},〃）=Pi:.Pm}

在此基礎(chǔ)上，

即取所有碓定化后不是終結(jié)狀態(tài)的狀態(tài)為的終結(jié)狀態(tài)。

為了證明，我們?cè)诘幕A(chǔ)上，其中，即所有確定化后的狀態(tài)

都為終結(jié)狀態(tài)。顯然

則又因?yàn)楣剩?/p>

同理容易證明

故，又因?yàn)?，?/p>

可知，構(gòu)造的是符合要求的。

XIX

zjszTszjsXT*zfsxTsZTSzT*ZT^XT*Z7SZTXxTszTszjsxT*ZT^XT^^TS/7^zTsZg*

K?>、],Z^!>

z|sZ7*Z7SXTSZTSZTSZgSZ7^ZlSZjSZTSZjSZT^ZTXZ7SZTSZ?*Z?S*TXZT^*TSZ?*ZtS^TX

14.構(gòu)造識(shí)別下列語(yǔ)言的￡-NFAo(XX賢培02282047)

(1){x|xe{0,1}+且x中含形如10110的子串}U{x|xe{0,1}+

和x的倒數(shù)第10個(gè)字符是1,且以01結(jié)尾}。

解:得到的￡-NFA如下所示：

⑵{x|xe{0,1}+且x中含形如10110的子串}{x|xe{0,1}+

和x的倒數(shù)第10個(gè)字符是1,且以01結(jié)尾}

解:得到的s-NFA如下所示:

（3）{xIxe{0,1}+且x中不含形如10110的子

串}U{x|x￡{0,1}+且x以0開(kāi)頭以1結(jié)尾}。

解：關(guān)鍵是構(gòu)造第一個(gè)FA,方法是設(shè)置5個(gè)狀態(tài)：

q0：表示開(kāi)始狀態(tài)，以及連續(xù)出現(xiàn)了兩個(gè)以上的0時(shí)所進(jìn)入

的狀態(tài)。

ql：表示q0狀態(tài)下接受到1時(shí)（即開(kāi)始狀態(tài)或2個(gè)以上的0

后輸入1時(shí)）所進(jìn)入的狀態(tài)。

q2：表示ql狀態(tài)下接受到。時(shí)（即開(kāi)始狀態(tài)或2個(gè)以上的0

后輸入10時(shí)）所進(jìn)入的狀態(tài)。

q3：表示q2狀態(tài)下接受到1時(shí)（即開(kāi)始狀態(tài)或2個(gè)以上的0

后輸入101時(shí)）所進(jìn)入的狀態(tài)。

q4:表示q3狀態(tài)下接受到1時(shí)（即開(kāi)始狀態(tài)或2個(gè)以上的0

后輸入1011時(shí)）所進(jìn)入的狀態(tài)。

故得到的￡-NFA如下所示:

(4){xIxe{0,1}+且x中不含形如00的子串}{x|xe{0,1}+且

x中不含形如11的子串}o

解:得到的￡-NFA如下所示:

另外，本題可以構(gòu)造DFA如下(其中qt為陷阱狀態(tài))：

0

⑸{XIxe{0,1）+且X中不含形如00的子串}Cl{X|x￡{0,1}+

且x中不含形如11的子串}。

解：由于xxx既不含形如00的子串，又不含形如11的子串，故

xxx只能是01相間的串。所以，得到的￡-NFA如下所示：

另外，本題可以構(gòu)造DFA如下（其中q+為陷阱狀態(tài)）：

0

VXKI>K|>K^VXK^^I>K^VXK^^1>V>

*1*^T>*T^^7**T**T**1**1**7*^J>*T**T**T**!**T*^7**T^*y*^7**y**1^*!**jNZ7**1SZ1^ZTS#TSzj^ZlSZjSZrsZT%ZTSZTNZ1*zTs*Ts*TN<f\

*i**lzs￡z*A**lz*lz

Zi>^|X^TSXI%ZjSZTXZT^Zl>ZjSXINZTSZ7%ZTS*|*ZTS#jSZ7%Xj>Xj><T>^1%

15.(1)根據(jù)NFAM3的狀態(tài)轉(zhuǎn)移函數(shù)，起始狀態(tài)qO的閉包為

-CLOSURE(qO)={q0,q2}。由此對(duì)以后每輸入一個(gè)字符后得到的新

狀態(tài)再做閉包，得到下表：(xx02282085)

狀態(tài)01

{qo.q2){qo,qi.q2){qo,qi.q2.q3)

{q0.ql.q2}{qo.q1.q2,q3}{qo.q1.q2.q3)

{qo.ql.q2.q3}{qo.q1.q2.q3}{qo.qi.q2.q?)

q0={qO,q2},ql={qO,ql,q2},q2={qO,ql,q2,q3},因

為q3為終止?fàn)顟B(tài)，所以q2={qO,ql,q2,q3}為終止?fàn)顟B(tài)

(2)又上述方法得

狀態(tài)01

{qi.q?){q3.qz){qo.q1.q2.q3}

{q.vq?)Iq3.q2){qo.qi.q3)

{qo.qi-}{quq2.q3){qo.q1.q2,q3}

{qo.qi.q3){q1.q2.q3}{qo.qi.q2.q?}

{q1.q2,q3}(q3.q2({qo.qi.q2.q?}

qO={ql,q3},ql={q3,q2},q2={qO,ql,q2,q3},q3={qO,

ql,q3},q4={ql,q2,q3}因?yàn)楦鳡顟B(tài)均含有終止?fàn)顟B(tài)，所以qO,ql,

q2,q3,q4均為終止?fàn)顟B(tài)

注：本題沒(méi)有必要按照NFA到DFA轉(zhuǎn)化的方法來(lái)做，而且從-NFA

到NFA轉(zhuǎn)化時(shí)狀態(tài)沒(méi)有必要改變，可以完全采用-NFA中的狀態(tài)

如（1）

狀態(tài)01

q。（開(kāi)始狀態(tài)）{qo.qi.q?qs){Qo.qi.q?,Qa}

{Qo.qi,q?,qa){Qi.qz.Q3)

q2{Qo,qi,q2,qal{qi.qz,qs)

q3（終止?fàn)顟B(tài)）{Qo,Qi,q?,P3){qo.qi,q2,qal

⑵

狀態(tài)01

qo（開(kāi)始狀態(tài)）{qiqjqa,1{qo.qi,q?,q3)

{q2}(qi.q?)

q2{,q2,q3){qo.q2.q3)

q3（終止?fàn)顟B(tài)）空{(diào)qo)

*X**1**>L**1**4**1<*X**J**1**1**L**4**>L**1**!>*.!<*J**^*L**J**4**4**>L**L*?b*

*1**T**T*>T**T**T**T**T**T**T**T**T**T**T**T**T**T**?**T**7**T**7**T*>T*^T**T**T**T**T**T**T*>T**T*

K1>x!>*I>、］/、］,、1,K|>K!XK!>

*T^*1*X7SZTSZTSzTsZg?ZjSZTSzj^

16.證明對(duì)于的FAM1=(Q1,El,5l,q01,Fl),FA

Ml=(Q2,￡2,52,q02,F2),存在FAM,

使得L(M)=L(M1)UL(M2)(xx02282072)

證明：不妨設(shè)QI與Q2的交集為空

(1)構(gòu)造M=(Q1UQ2U{q0},Z,b,qO,F)其中：

1)S=S1US=F1UF2

2)8(q0,￡)={qOl,q02)對(duì)于q￡Ql,aW￡16(q,

a)=61(q,a)

對(duì)于q￡Q2,a0Z2,6(q,a)=82(q,a)

(3)證明：

1)首先證L(M1)UL(M2)￡L(M)

設(shè)xeL(Ml)UL(M2),從而有x￡L(M1)或者xEL(M2),

當(dāng)xWL(M1)時(shí)

5l(q01,x)eFl

由M的定義可得:

5(qO,x)=6(qO,ex)=6(8(qO,￡),

x)=5({qOl,q02},x)=5(qOl,x)U8(q02,x)

二51(qOl,x)U8(qOl,x)eFlU8(qOl,x)即

xeL(M)

同理可證當(dāng)xL(M2)時(shí)x￡L(M)

故L(Ml)UL(M2)WL(M)

2)再證明L(M)WL(Ml)UL(M2)

設(shè)x￡L(M)則6(qO,x)eF

由M的定義：

8(qO,x)=5(qO,ex)=8(8(qO,￡),

x)=S({qOl,q02},x)=S(qOl,x)U8(q02,x)

如果是5(qOl,x)因?yàn)镼I與Q2的交集為空而且6(qO,x)

eFF=F1UF2則

5(qOl,x)=51(qOl,x)GF1因此x￡L(Ml)

如果是§(q02,x)因?yàn)镼I與Q2的交集為空而且5(qQ,x)

eFF=F1UF2則

6(q02,x)=52(q02,x)eFl因此x￡L(M2)

因此XeL(Ml)UL(M2)L(M)eL(Ml)UL(M2)得證

因此L(M)=L(M1)UL(M2)

KT>Kl>KI>S>|>K