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

第三章作業(yè)答案

1.已知DFAM1與M2如圖3—18所示。(敖雪峰02282068)

(I)請(qǐng)分別給出它們?cè)谔幚碜址?011(X)1的過程中經(jīng)過的狀態(tài)序列。

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

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

解答：(1)M1在處理10110。1的過程中經(jīng)過的狀態(tài)序列為40434僧3口2434僧3；

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

(2)考慮到用形式語言表示，用自然語言好像不是那么簡(jiǎn)單，所以用圖上作業(yè)法把它們用正則

表達(dá)式來描述：

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

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

存市中本主衣字字市存本中本市東市孝辛市本東字東衣字才未存幸赤字小本字4市存東中家市亭市孝豐孝奉市本市*字字市存本赤本市*中字市今未本市孝本存家市本市才本存本市

2.構(gòu)造下列語言的DFA（陶文婿02282085）

(1){0,I}*

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

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

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

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

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

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

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

x0時(shí)，x的苜字符為1}

1.以。開頭的事不被接受，故設(shè)置陷阱狀態(tài)，當(dāng)DFA在啟動(dòng)狀態(tài)讀入的符號(hào)為0,則進(jìn)

入陷阱狀態(tài)

2.設(shè)置7個(gè)狀態(tài)：起先狀態(tài)q“qo：除以5余0的等價(jià)類，qi,除以5余1的等價(jià)類,qz僚以5

余2的等價(jià)類，q上除以5余3的等價(jià)類，q,：除以5余4的等價(jià)類，接受狀態(tài)中

3.狀態(tài)轉(zhuǎn)移表為

狀態(tài)0i

q。qiq2

qiq3q2

M2qo

q3qiqz

q4q?q，

（8）{x|x{0,i}+且x的第十個(gè)字符為1}

（設(shè)置一個(gè)陷阱狀態(tài)，一旦發(fā)覺X的第十個(gè)字符為（），進(jìn)入陷阱狀態(tài)）

（9）{x|x{0,1}+且x以（）開頭以1結(jié)尾}

（設(shè)置陷阱狀態(tài)，當(dāng)?shù)谝粋€(gè)字符為1時(shí)，進(jìn)入陷阱狀態(tài)）

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

(Il){X|x{0,1}+且假如x以1結(jié)尾，則它的長(zhǎng)度為偶數(shù)：假如x以0結(jié)尾，則它的長(zhǎng)

度為奇數(shù)}

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

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

q1：x的長(zhǎng)度為奇且以0結(jié)尾的等價(jià)類

qzx的長(zhǎng)度為奇且以I結(jié)尾的等價(jià)類

q3：x的長(zhǎng)度為偶且以0結(jié)尾的等價(jià)類

q4：x的長(zhǎng)度為偶且以1結(jié)尾的等價(jià)類

5,6,7,8,9

(13)

***********木*水***************%**********；)：*；)：********木*****************次*；｝；*******

3(1)(張友坤02282061)

0

1={0,1}

Set(q0)={x|XGZ*}

(2)

￡={0,1}

Set(qO)=￡

Sct(ql)={x|xeE+)

(3)

Z={0J}

Set(q0)=￡

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

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

(4)

X={0J}

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

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

⑸

n

oi1o

Z={o,i}

Set(qO)=(xx￡E",并且X￡｛0｝*或者x中含形如100的子串｝

Set(ql)={xxe并且x中含形如1的子串｝

Set(q2)={xXG并且x中含形如10的子串｝

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

Sct(q4)={xXGX",并且X中含形如10如的子串｝

Set(q5)={xXGZ*,并且X中含形如10110的子串）

Z={O51}

Set(q0)={￡}

Set(ql)={x|xe{0'})

Set(q2)={x|xeZ并且x中不含形如10110的子串而且x中含有I}

Set(q3)={x|XGZ",并且x中不含形如10110的子串而且x中含有1}

L={0J}

Set(qs)={8}

Set(qe)={0}

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

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

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

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

Set(qO)={x|xeZ?，并且把x看成二進(jìn)制數(shù)時(shí)，x%5=0并且x不為0}

(8)

M={Q,Z@,qo,F}

Q={qo,qi,q2,...qio}

I={0,1}

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

(q>,0)=8(qi,])=q<i+i>

5(q9,l)=qio

(qio,O)=6(qio,l)=qio

F={qio}

Set(qO)={￡}

Set(ql)={(),!}

Set(q2)={x|XGZ?，尹且|x|=2)

Set(q3)={xIxeZ，且|x|=3}

Sct(q4)={x|xeZ.，步且|x|=4}

Set(q5)={x|xeZ+,爐且|x|=5}

Sct(q6)={x|XG并且|x|二6}

Set(q7)={xIxeZ?，走且|x|=7}

Set(q8)={xIxeZ+,并且|x|二8}

Set(q9)={x|XG2?,尹且|x|=9}

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

(9)M=(Q,Z?,qo,F}

Q={qo，qi，q2)

Z={0d}

6(qo,O)=qi

Z>(qhO)=qi

b(qi,l)=q2

b(q2』)=q2

#(q2,0)=qi

F={q2}

Set(qO)={￡}

Set(ql)={x|xeZ+,方且x以0開頭以0結(jié)尾}

Set(q2)={x|XGZ?，尹且x以0開頭以I結(jié)尾}

(10)M={Q,Z,(y,qo,F)

Q={qo,qi,q2}

X={()1}

8(qo,O)=qo

3(qo,l)=qi

^>(qi,O)=qi

3(qi,1)=q2

S(q21)=q2

3(q2,0)=qi

F={q?}

Set(q0)={0}*

Set(ql)={x|XGZ+,尹且x中只有一個(gè)1}

Set(q2)={x|xeZ;尹且x至少有倆個(gè)I}

(ll)M={Q,E,5,qo,F}

Q={qo,qi,q2,q3,q4}

Z={()1}

8(qo,O)=qi

S(qo,l)=q4

d(qi,0)=q3

5(qi,l)=q2

S(q21)=q4

5(q2,0)=q?

S(q3,0)=qi

^(q.%l)=q4

S(q41)=q2

3(q4,0)=q3

F={qo,qi,q2}

Set(q0)={￡}

Set(ql)={xIxeZ?，以0結(jié)尾，長(zhǎng)度為奇數(shù)}

Set(q2)={x|xeZ?，以1結(jié)尾，長(zhǎng)度為偶數(shù)}

Set(q3)={x|xeZ?，以0結(jié)尾，長(zhǎng)度為偶數(shù)}

Set(q4)=(x|XGZ?，以1結(jié)尾，長(zhǎng)度為奇數(shù)}

(12)

M={Q,Z?,qo,F}

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

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

F={qLq2,q4}

5(q(),0)=ql

^(qo,H2|3|4|5|6|7|8|9)=q2

3(q1,.)=q2

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

(y(q2,.)=q3

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

<J(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)=0

(14)

------

Set（qO）={￡}

******木********木*木*木左太東*水木水*木京********本*木*木*****木木*****木*木木木木************木木****

4在例3-6中，狀態(tài)采納仇卬生...//的形式，它比較清晰地表達(dá)出該狀態(tài)所對(duì)應(yīng)的記憶內(nèi)

容，給我們解決此問題帶來了很大的便利，我們是否可以干脆用生…%1代替

仇2呢？假如能，為什么？假如不能，又是為什么？從今問題的探討，你能總

結(jié)出什么來？（唐明珠02282084）

答：我認(rèn)為能夠干脆用［《生…《」代替以《生…明〕，因?yàn)樵诶?-6中，仇《生…。,」只是一

種新的表示方法，用來表示狀態(tài)存儲(chǔ)的字符，這樣就省去了在5中逐一給出每一個(gè)詳細(xì)

的輸入字符和狀態(tài)的定義。它的作用在于使FA中狀態(tài)定義更加簡(jiǎn)潔。

得到結(jié)論：在今后描述FA時(shí)，應(yīng)當(dāng)依據(jù)詳細(xì)的狀況，運(yùn)用適當(dāng)?shù)姆椒ā?/p>

4*赤本小衣市孝市存布市*字才市存本中東亦字木衣幸存幸存*赤字市余字4市中東中出市亭市存幸存亭赤本小李幸存奉市幸東*小衣市本爾孝幸中市孝本赤字市今市才小存布市

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

解：⑴陷阱狀態(tài)（課本97頁）：指在其它狀態(tài)下發(fā)覺輸入串不行能是該FA所識(shí)別的句子

時(shí)所進(jìn)入的狀態(tài)。FA一旦進(jìn)入該狀態(tài)，就無法離開，并在此狀態(tài)下，讀完輸入串中

剩余的字符。

⑵不行達(dá)狀態(tài)（課本108頁）：指從FA的起先狀態(tài)動(dòng)身，不行能到達(dá)的狀態(tài)。就FA

的狀態(tài)轉(zhuǎn)移圖來說，就是不存在從起先狀態(tài)對(duì)應(yīng)的頂點(diǎn)動(dòng)身，到達(dá)該狀態(tài)對(duì)應(yīng)頂點(diǎn)

的路徑。

⑶從兩者的定義可見：相對(duì)于不行達(dá)狀態(tài)來說，陷阱狀態(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)。

注：此題目有問題，可以將題設(shè)改為：x中。和1個(gè)數(shù)相等且交替出現(xiàn)

6.證明：題目有不嚴(yán)密之處，圖中給出DFA與題目中的語言L（M）={x|xx{0,1「且

x中0的個(gè)數(shù)和1的個(gè)數(shù)相等}不完全對(duì)應(yīng)，首先圖中的DFA可接受空字符串，而L（M）

不接受，其次，對(duì)于有些句子，例如1100,L（M）可以接受，但DFA不接受

（I）依據(jù)圖中的DFA可看出，右下角的狀態(tài)為陷阱狀態(tài)，所以去除陷阱狀態(tài)

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

SfOA

4-1S|1

SfTB

3-0S|0

將IS,1代入S—OA；0S,0代入Sf13得

5^015101

10S|10

由此可以看出該文法接受的語言為L(zhǎng)={(10|01)*},明顯01或10分別是作為整體出現(xiàn)的，

所以L(M)中0和1的個(gè)數(shù)相等。

**水*木******木******木*水***木******木*求****木*木******木木木*水******木*木*求******木木*

7.設(shè)DFAM=(Q,Z,b,%,F),證明：對(duì)于Vx,y￡Z”,”Q?(dA＞，)=30(q,x),y)

注：采納歸納證明的思路

證明：(周期律02282067)

首先對(duì)y歸納，對(duì)隨意x來說，卜|=。時(shí)，即y=e

依據(jù)DFA定義6(%￡)=夕,6(小孫)=6(/幻=3(5(%無),￡)=5(3(小外,丁),故原式

成立。

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

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

依據(jù)DFA定義5(dxa)=x),a),awZ,故

5(",肛)=d(q,xwa)=5(5(，/,xw),a)=b(3(b(c/,x),w),a)=5(5(c/,x),vva)=5(5(*,x),y)

原式成立，

同理可證，對(duì)隨意的y來說，結(jié)論也是成立的。

綜上所述，原式得證

8.證明:對(duì)于隨意的DFAMi=(Q,2,6,qo,B)存在DFAM2NQR,"qoR),(馮蕊02282075)

使得L(M2)=Z"-L(Mi)o

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

設(shè)DFAM,=(Q.2,6,qo,Fi)取DFAM2=(Q,S,6,q°.Q—F。

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

對(duì)隨意xE*

xL(M2)=2"—L(Mi)6(q,x)Q—Fi8(q,x)Q并且6(q,x)F|

x3*并且xL(Mi)xX*—L(Mi)

9.對(duì)于隨意的DFAM|=(Qi,Z,6],qoi,B),請(qǐng)構(gòu)造DFAMI=(Q2,E,82,qo2,F2),使得

T

L(M))=L(M2)O其中L(M)T={x|xT￡L(M)}(褚穎娜02282072)

(1)構(gòu)造￡?NFAM使得L(M)=L(Mi)?e-NFAM=(Q,E,6,q0,{q0I})其中:

1)Q=QiU{qo],qoQi

2)對(duì)于q,pWQi.a￡E，假如6i(q,a尸p,q￡6(p,a)

3)§(qo,￡)=Fi

(2)證明：L(M尸L(Mi)T

對(duì)x=aia2...am^L(M)

QoSia2…a?)pQfa2…a”ikaiqia2…a?)卜a】a?q2…a”[卜…卜ai32-??Qin-iam

Hia2...amqoi

6

其中qf￡5(q(),￡),6(qf,ai),q2^(qi,a2),...qoi^(q.n-i,am)并且qf￡Fi

6

則8i(qoi,am)=qllbi,61(qin.ham.i)=qm-2,...i(q2,a2)=qi&i(qi,ai)=qf

囚此qoi3inSin-1.--31卜a1]】Qm-l^ni-1-?-31Rain3in-l...922231卜Uin-I...<12CjlHl

卜amam」…a2aq

因此amani...ai￡L(Mi)即XTGL(MI)

T=

同理可證對(duì)于x=aia2...amGL(Mi)xamain.i...aiEL(M))

L(M)=L(Mi)T得記

(3)將￡-NFAM確定化

首先構(gòu)造與￡-NFAM=(Q,E,6,qo,{q0I})等價(jià)的NFAM3KQ,E,62,qo,{qoi})

A

其中對(duì)于(q,a)￡Q*E62(q,a)=(q,a)

然后依據(jù)以前學(xué)過的方法構(gòu)造與NFAM3=(Q,E,62,qo,{qoi))等價(jià)的DFA

Mi=(QhE,6],[q31,Fi)其中:Qi=2^F1={qOi}

6i([qi.q2...qn]^)=[pi,p2,.-.,pn]當(dāng)且僅當(dāng)$2({qi.q2….小},a)={pi,p2,...,pn}

*************************************************************:§:*****************

注：此題(10題)張友坤、吳玉涵所做完全一樣！！

10、構(gòu)造識(shí)別下列語言的NFA(吳玉涵02282091)

⑴{1卜￡{()』}'且沖不含形如00的子串}

1

__________

⑵{小￡{0,1}+且沖含形如lOUOfi勺子串}

⑶{斗相{0,1}+且沖不含形如10110的子串}

0.1

0,

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

A：}

(5){琲丫￡{0』}'目/以0開頭以1結(jié)尾}

0.1

(6){XXG{0,1}+且時(shí)1至少含有兩個(gè)1}

⑺*X￡{0,l}“且如果A以1結(jié)尾，則它的長(zhǎng)度為偶數(shù);

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

s0,I

0

，I

(8){xXG{()4}?且X的首字符和尾字符相等}

⑼{.皿/￡{()」「}

這是最基本的單元，其他的可以通過這個(gè)逐級(jí)構(gòu)造出來，以滿意題目要求。

11.依據(jù)給定的NFA,構(gòu)造與之等價(jià)的DFA.(吳丹02282090)

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

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

012

起先狀態(tài)q0{qO,ql){q0，q2}{q0,q2]

qi叫0}0{q2}

q20{q3,ql}{q2,ql]

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

解答:

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

012

起先狀態(tài)qo[qO,ql][qO,q2]lq0,q2]

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

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

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

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

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

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

[qO,ql]

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

qO°<Q

0)122o1

1,2I/1\oy

2j0,1卅j

『豚qi，q2，q3i

[q(),q2]mom"】AJ

一i一

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

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

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

012

起先狀態(tài)q0{ql,q3}{ql}(q0)

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

q2{q3.q2}{q0}{q2}

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

q30{q。}{q3}

解答:

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

012

起先狀態(tài)q0[ql,q3][ql][q0]

[qhq3]fq2][q0,ql,q2]Iql，q3]

卬］lq2][ql,q2][qU

[q2Jlq2,q3J(qO][q2j

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

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

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

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

[q0,ql,q2]

[ql,q314j2

,2-J。Iq3,ql,q2]

2/Pl時(shí)。必工^

1

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

**木*求******木*求******求************求****次*求********木***************水***求******

12.證明對(duì)于隨意的NFA,存在與之等價(jià)的NFA,該NFA最多只有一個(gè)終止?fàn)顟B(tài)

(劉鉉02282083)

證明：對(duì)于隨意的NFAM=(Q,Z,5,q(),F),我們假如能構(gòu)造出一個(gè)只有一個(gè)終止?fàn)?/p>

態(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)無需變更，該NFA即為滿意條件的NFA

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

弧復(fù)制到該狀態(tài)，，此時(shí)這個(gè)終止?fàn)顟B(tài)為新狀態(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)

**************************************************************************字****

13.試給出一個(gè)構(gòu)造方法，對(duì)于隨意的NFA〃：=(Q1,Z，d，4o，A)，構(gòu)造NFA

%=(。2，工必//2)，使得L(M2)=Z*—L(M)

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

證明:（周期律02282067）

首先構(gòu)造一個(gè)與NFA等價(jià)的DFA，歷3依據(jù)定理3.?（P106）,L（M、）=

構(gòu)造％=@，工兩[如，入），其中

。3=2%居={M,p2…P,"I{Pl，P2…P〃JQ0，{Pl，P2…P,〃}n耳工。},{Pl,P2...PM）qQ,。wZ

“（⑷...gJa）=[p...p,"od（{/…或},a）={z...pm]

在此基礎(chǔ)上M2,2=Q?2=5B={[PL]I出…P,”]n居=0}

即取全部確定化后不是終結(jié)狀態(tài)的狀態(tài)為M2的終結(jié)狀態(tài)。

為了證明〃"2）=2*一"加3），我們?cè)冢サ幕A(chǔ)上=（。4，￡必先,已），其

中。4=。3，久=&，吊二。4，即全部M確定化后的狀態(tài)都為終結(jié)狀態(tài)。明顯

L（〃4）=Z*，

VxeL（M2\貝IJ次外,幻0鳥工。=＞方（%,1）。工工。=/任〃/3），又因?yàn)?/p>

5（%,人）￡。3nS（00,x）￡尸4n演%,x）eL（M4）=^\故XGZ"-L（M），

故〃/2）q2*一（%）

同理簡(jiǎn)單證明〃加2）3Z?一^^3）

故〃加2）=2*—〃加3），又因?yàn)長(zhǎng)（“3）=L（M]），故〃"2）=Z"—"MJ

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

*木木*木*求****木*木*木********水*木**木*木木木*木***木木*木*木*木****木*****木木***木********水*木***木木

14.構(gòu)造識(shí)別下列語言的￡-卬人。（吳賢培02282047）

（1）{X|xe{0,1}?且X中含形如10110的子串}U{X|xe{0,1}+和x的倒數(shù)第10

個(gè)字符是1,且以01結(jié)尾鼠

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

0,I

⑵{x|x￡{0,1}.且x中含形如10110的子串}{X|XE{（）,1）*和x的倒數(shù)第10個(gè)字

符是1,且以01結(jié)尾}

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

S

⑶{x|x￡{0,1}'且x中不含形如10110的子串}U{x|x￡{0,1}一且x以0開頭以1

結(jié)尾}。

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

qo：表示起先狀態(tài)，以及連續(xù)出現(xiàn)了兩個(gè)以上的。時(shí)所進(jìn)入的狀態(tài)。

q1：表示q0狀態(tài)下接受到1時(shí)（即起先狀態(tài)或2個(gè)以上的0后輸入1時(shí)）所進(jìn)入

的狀態(tài)。

q＞：表示卬狀態(tài)下接受到0時(shí)（即起先狀態(tài)或2個(gè)以上的0后輸入10時(shí)）所進(jìn)入

的狀態(tài)。

q；,：表示qz狀態(tài)下接受到1時(shí)（即起先狀態(tài)或2個(gè)以上的0后輸入101時(shí)）所進(jìn)入

的狀態(tài)。

qi：表示q?狀態(tài)下接受到1時(shí)（即起先狀態(tài)或2個(gè)以上的0后輸入1011時(shí)）所進(jìn)

入的狀態(tài)。

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

⑷{xIxU[0,1「且X中不含形如00的子串）{xIXU（0,1}'且X中不含形如11的

子串}。

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

0.I0,I

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

0

⑸{x|xe{0,1},且x中不含形如00的子串}G{X|x￡{0,1}.且x中不含形如11的子

串}。

解：由于x中既不含形如00的子串，又不含形如11的子串，故x中只能是01相間的

串。所以，得到的￡-NFA如下所示：

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

********************木*****************木***求***求**木**********求********木*********

15.(I)依據(jù)NFAM3的狀態(tài)轉(zhuǎn)移函數(shù)，起始狀態(tài)qo的閉包為-CLOSURE(q0)={qoq?}。

由此對(duì)以后每輸入一個(gè)字符后得到的新狀態(tài)再做閉包，得到下表：(陶文靖02282085)

狀態(tài)01

{qo.q?}{qo.qi.q2){qo.qi.q2.qs!

{qo.qi.qi}{qo.qi.q2,q”{qo.qi-}

{qo.qi.qz.qa){qo.q1.q2.q3({qo.q1.q2,q3}

qo={qo.qi}>q1dqo.q1.q2}，q2Mqo.q1.q2.q3}，因?yàn)閝3為終止?fàn)顟B(tài),所以q2={qo.qi.qz.q3}

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

（2）又上述方法得

狀態(tài)01

{qi.q?}{q3.qz}{qo,ql.q2.q3}

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

{qo.qi.q&q^){ql.q2,q3}{qo.qi.q2.q.3}

{qo.qi.qs}{qi.qz.q?){qo.qi.qz.qj}

{q1.q2.q3}{q3.qz}{Qo.qi.qz.q?}

qo={qi.qs},qi={q3.q?}>q2Mqo.q1.q2.q3)，q3Jqo.q1.q3}，q4={qi-q2.qs}因?yàn)楦鳡顟B(tài)均含

有終止?fàn)顟B(tài)，所以qo,qi，q?.q3.q4均為終止?fàn)顟B(tài)

注：本題沒有必要依據(jù)NFA到DFA轉(zhuǎn)化的方法來做，而且從-NFA到NFA轉(zhuǎn)化時(shí)狀態(tài)沒有

必要變更，可以完全采納-NFA中的狀態(tài)

如（1）

狀態(tài)01

q。（起先狀態(tài)）{qo.qi.q?q3j{Qo.Qi,qz,Q3}

q?{qo.qi.q2.qJ{q>,q2,qJ

q2{Qo.qi,qz,qsl(qi.Q2.qa)

{qo.qi.q?,qa){qo.qi,q?,qal

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

⑵

狀態(tài)01

5（起先狀態(tài)）{qiQ2qa.1{qo.qi.qz.qa)

qi{q2}{qi.qz)

q2{.q?,qa){qo.qz,q3)

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

*******************************************************************************

16.證明對(duì)于的FAMi=Q,￡i,51,qoi,B),FAMI=(Q2,E2,82,qo2,F2),FAM,

使得L(M尸L(MI)UL(M2)(褚穎娜02282072)

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

(1)構(gòu)造M=(QiUQ2U{qo),Z,8,qo,F)其中:

1)E=E|UE2F=F|UF2

2)3(qo,￡)={qoi,q(m}對(duì)于q^Qi.aeEiS(q,a)=5j(q,a)

e

對(duì)于qQ2.ae￡2,6(q,a)=82(q,a)

(3)證明：

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

設(shè)x￡L(MI)UL(M2)，從而有x￡L(MD或者xeL(M2),當(dāng)x￡L(M?時(shí)

5i(qoi,x)GFi

由M的定義可得：

5

(qo,x)=S(qo,￡x)=8(8(qo,*),x)=S({qoi,q(m},x)=8(q0l,x)U6(q02,x)

=8i(qoi,x)U8(qoi,x)GFiU5(qOi,x)即xEL(M)

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

故L(MI)UL(M2)EL(M)

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

設(shè)x￡L(M)則6(q0,x)WF

由M的定義：

5

(qo,x)=S(q(),￡x)=8(8(q0,￡),x)=S({q()i,q()2},x)=8(q0),x)U8(q02,x)

假如是3(qoi,x)因?yàn)镼i與Q2的交集為空而且3(q°,x)WFF=FIUF2則

8(qoi,x)=6](qo],x)￡Fi因此x￡L(Mi)

假如是6(q*x)因?yàn)镼i與Q2的交集為空而且3(qo,x)￡FF=FIUF2則

S(qo2,x)=62(qo2,x)GFi因此x￡L(Mz)

因此x￡L(Mi)UL(M2)L(M)GL(MI)UL(M2)得證

因此L(M尸L(MI)UL(M2)

*******************************************************************************

(唐明珠02282084)

17證明：對(duì)于隨意的FAM]=(0],Z[b],40[,耳),~4用2=(。2，工2?2國02，工)，

存在FAM,使得L(M)=UM,)UM2).

證明：令”=(02。2，￡小[3，{口})，其中6的定義為:

1)對(duì)VqWQHfi},aGLU{￡}

6(q,a)=Sl(q?a)；

2)對(duì)XZq￡Q2-{f2},aeLU{e}

S(q?a)=62(q?a)：

3)6ge)={q02}

要證L(M)=L(MJL(MQ,

只需證明,L(M,)￡(/W2)OL(M)

1.證明L(M1)L(M2)qL(M)

法CL(M)L(M2)，從而有X￡〃"1)并由2￡〃“2)，

使得X=Xix2

M在處理的過程中，經(jīng)過的狀態(tài)全部都題沖的狀態(tài)，所以在定義

MW,對(duì)sW0MWz?(q,x)=3[(q,a)

故5(心閂)=一(%”，/)="}

例2在處理々的過程中,經(jīng)過的狀態(tài)全部都她22中的狀態(tài),所以在定義

M時(shí)，對(duì)VqeQ^ae￡b(g,x)=62(q,a)

b(%2，x)=aq。],1)={力}

下面證明xGL(M)

5(%],幻=3(%],為超)

=鳳3(%],王)/2)

二5301，石),々)

=—，%2)

=3(力,%)

=6(6(/,￡),/)

=3(%2，工2)

=%(%2?X2)

={『2}

即得證xeL(M)

2)再證明

設(shè)xwL(M),即

bQi.x)—

由于M是從外?啟動(dòng)的，由M的定義可知M要達(dá)到狀凝，必須

先到/；由于除了對(duì)應(yīng)狀態(tài)轉(zhuǎn)腐I數(shù)式/九￡)=@2}的移動(dòng)

外，不存在對(duì)出發(fā)的任何其他移動(dòng)而且該移動(dòng)蹤的必經(jīng)

移動(dòng)，所以，比存在X的前綴m卻后綴X2,使得X=X|X2,并且X1

將M從狀態(tài)如引導(dǎo)到狀態(tài)九G將M從狀態(tài)強(qiáng)引導(dǎo)到狀態(tài)

.即

方(為1，])=》(901內(nèi)々)

=^(/pX2)

二5(力，夕2)

二方(金2，犬2)

={/2}

其中，

5(夕01一)="},說明水夕01，再)="}；

6(%，％2)={y2}，說明&(%2/2)={72}

這表明

X2eL(M2)

從而

x=XjX2GL(MX)L(M2)

故L(M)qL(%)L(M2)

綜上所述，

L(M)=L(M])L(M2

*******************************************************************************

（吳丹02282090）

18.證明：對(duì)于任意的FAM尸（Q1Zeq。』），F(xiàn)AM2=（Q2N血,q02月）

存在FAM,使得L（M）=L（MjnL（M2）。

證明：不妨將這些FA看成DFA

F

取14=8*（22,210二，b，{q（H，q02}?）

對(duì)于1€二（122,8加）€（2，佃切，2）=［用1,a）,（p,a）］.

（1）設(shè)：xGL（M）則3x=xlx2...口其中七（，￡［1,攵］|￡21門工2

使得b（［q,p］,M=［g（q,耳）,心8，戈i）］

x/eL（M1）nL（M2）=>XGL（M1）r|L（M2）

從而可得L（M）qL（Mjr|L（M2）

（2）設(shè)：x￡L（MjnL（M2）則=..以其中w0用）w*DE2

有d（q,xi）且司⑺，xi）從而使得

4（q，xz）=^（［q,p］,xi）;&（p,H）=3（［q,p］,xz）

xieL（M）=>xeL（M）

從而可得L（MjnL（M2）qL（M）

綜合⑴⑵可得L（M）=L（MjnL（M2卜

又因?yàn)镕A和DFA具有等價(jià)性，所以原命題得證。

***************木********************************米****木*************木*木木******

19、總結(jié)本章定義的全部FA,歸納出它們的特點(diǎn)，指出它們之間的差別。（吳玉涵02282091）

本章學(xué)習(xí)了DFA,NFA,e-NFA,2DFA和2NFA

全部的FA都是一個(gè)五元組M=（Q,2,6,q（）,F）

最大的區(qū)分就是狀態(tài)轉(zhuǎn)移函數(shù)6

對(duì)于DFA,字母表中的每個(gè)字母都有唯一確定的狀態(tài)轉(zhuǎn)移函數(shù)。也就是說V8（q,a）eQ

XX,q￡Q,aWE只有哇一確定的狀態(tài)。

對(duì)于NFA,對(duì)于字母表中的每個(gè)輸入字符可以有不同的狀態(tài)轉(zhuǎn)移，對(duì)于￡串，是一個(gè)到自

身的移動(dòng)。

對(duì)于￡?NFA,是指在不接受任何字符的狀況下，自動(dòng)機(jī)的狀態(tài)可以發(fā)身轉(zhuǎn)移。

對(duì)于2DFA,對(duì)于字母表中的每個(gè)字符，對(duì)于每個(gè)狀態(tài)都有唯一的狀態(tài)轉(zhuǎn)移，即V5（q,a）

￡QX2,q￡Q,a￡2只有唯一確定的狀態(tài)。與DFA不同的是，2DFA的讀頭可以在一次

狀態(tài)轉(zhuǎn)移中不移動(dòng)，或者回退一個(gè)，或者向下讀一個(gè)。

對(duì)于2NFA,與2DFA相像，但是并不是對(duì)于字母表中的每個(gè)輸入字符都有轉(zhuǎn)移函數(shù)，2NFA

與2DFA的區(qū)分類似于DFA與NFA的區(qū)分。