第三章作業答案

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

(I)請分別給出它們在處理字符串1011(X)1的過程中經過的狀態序列。

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

圖3—18兩個不同的DFA

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

M2在處理1011001的過程中經過的狀態序列為qoq2q3qiq3q2q3qi；

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

表達式來描述：

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

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

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

2.構造下列語言的DFA（陶文婿02282085）

(1){0,I}*

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

(設置一個陷阱狀態，一旦發覺有00的子串，就進入陷阱狀態)

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

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

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

(設置一個陷阱狀態，一旦發覺有()0的子串，就進入陷阱狀態)

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

x0時，x的苜字符為1}

1.以。開頭的事不被接受，故設置陷阱狀態，當DFA在啟動狀態讀入的符號為0,則進

入陷阱狀態

2.設置7個狀態：起先狀態q“qo：除以5余0的等價類，qi,除以5余1的等價類,qz僚以5

余2的等價類，q上除以5余3的等價類，q,：除以5余4的等價類，接受狀態中

3.狀態轉移表為

狀態0i

q。qiq2

qiq3q2

M2qo

q3qiqz

q4q?q，

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

（設置一個陷阱狀態，一旦發覺X的第十個字符為（），進入陷阱狀態）

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

（設置陷阱狀態，當第一個字符為1時，進入陷阱狀態）

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

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

度為奇數}

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

qo：［］的等價類，對應的狀態為終止狀態

q1：x的長度為奇且以0結尾的等價類

qzx的長度為奇且以I結尾的等價類

q3：x的長度為偶且以0結尾的等價類

q4：x的長度為偶且以1結尾的等價類

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看成二進制數時，x%5=1}

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

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

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

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

(8)

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

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

I={0,1}

當0<=i<=8時候，

(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的第十個字符是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結尾}

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

(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中只有一個1}

Set(q2)={x|xeZ;尹且x至少有倆個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結尾，長度為奇數}

Set(q2)={x|xeZ?，以1結尾，長度為偶數}

Set(q3)={x|xeZ?，以0結尾，長度為偶數}

Set(q4)=(x|XGZ?，以1結尾，長度為奇數}

(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)={十進制正整數}

Set(q3)={十進制非負整數后面接個小數點.}

Set(q4)={十進制正小數}

(13)

Set(qO)={￡}

Set(qO)=0

(14)

------

Set（qO）={￡}

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

4在例3-6中，狀態采納仇卬生...//的形式，它比較清晰地表達出該狀態所對應的記憶內

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

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

結出什么來？（唐明珠02282084）

答：我認為能夠干脆用［《生…《」代替以《生…明〕，因為在例3-6中，仇《生…。,」只是一

種新的表示方法，用來表示狀態存儲的字符，這樣就省去了在5中逐一給出每一個詳細

的輸入字符和狀態的定義。它的作用在于使FA中狀態定義更加簡潔。

得到結論：在今后描述FA時，應當依據詳細的狀況，運用適當的方法。

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

5.試區分FA中的陷阱狀態和不行達狀態。（吳賢培02282047）

解：⑴陷阱狀態（課本97頁）：指在其它狀態下發覺輸入串不行能是該FA所識別的句子

時所進入的狀態。FA一旦進入該狀態，就無法離開，并在此狀態下，讀完輸入串中

剩余的字符。

⑵不行達狀態（課本108頁）：指從FA的起先狀態動身，不行能到達的狀態。就FA

的狀態轉移圖來說，就是不存在從起先狀態對應的頂點動身，到達該狀態對應頂點

的路徑。

⑶從兩者的定義可見：相對于不行達狀態來說，陷阱狀態是可達的。但是，它們都是

狀態轉移圖中的非正常狀態。假如從狀態轉移圖中的狀態引一條弧到不行達狀態，

同時不行達狀態全部的移動都是到自身。這樣，不行達狀態就變成了陷阱狀態。

注：此題目有問題，可以將題設改為：x中。和1個數相等且交替出現

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

x中0的個數和1的個數相等}不完全對應，首先圖中的DFA可接受空字符串，而L（M）

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

（I）依據圖中的DFA可看出，右下角的狀態為陷阱狀態，所以去除陷阱狀態

（2）由DFA可構造出與其對應的右線性文法：（劉鈕02282083）

SfOA

4-1S|1

SfTB

3-0S|0

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

5^015101

10S|10

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

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

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

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

注：采納歸納證明的思路

證明：(周期律02282067)

首先對y歸納，對隨意x來說，卜|=。時，即y=e

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

成立。

當|yl=n時，假設原式成立，故當|y|=n+l時，

不妨設y=wa,|w|=n,|a|=1

依據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)

原式成立，

同理可證，對隨意的y來說，結論也是成立的。

綜上所述，原式得證

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

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

證明：(1)構造M2。

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

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

對隨意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.對于隨意的DFAM|=(Qi,Z,6],qoi,B),請構造DFAMI=(Q2,E,82,qo2,F2),使得

T

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

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

1)Q=QiU{qo],qoQi

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

3)§(qo,￡)=Fi

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

對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=

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

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

(3)將￡-NFAM確定化

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

A

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

然后依據以前學過的方法構造與NFAM3=(Q,E,62,qo,{qoi))等價的DFA

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

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

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

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

10、構造識別下列語言的NFA(吳玉涵02282091)

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

1

__________

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

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

0.1

0,

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

A：}

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

0.1

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

⑺*X￡{0,l}“且如果A以1結尾，則它的長度為偶數;

如果以0結尾，則它的長度為奇數}

s0,I

0

，I

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

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

這是最基本的單元，其他的可以通過這個逐級構造出來，以滿意題目要求。

11.依據給定的NFA,構造與之等價的DFA.(吳丹02282090)

(1)NFAMi的狀態轉移函數如表3-9

狀態說明狀態輸入字符

012

起先狀態q0{qO,ql){q0，q2}{q0,q2]

qi叫0}0{q2}

q20{q3,ql}{q2,ql]

終止狀態q3(q3,q2){q3}{q0}

解答:

狀態說明狀態輸入字符

012

起先狀態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]

終止狀態[qO,qLq3][q0,ql,q2,q3][qO,q2,q3][qO,ql,q2]

終止狀態[qO,q2,q3][q0,ql,q2,q3][q0,ql,q2,q3]IqO.q2]

終止狀態[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等價的DFA

(2)NFAM2的狀態轉移函數如表3-10

狀態說明狀態輸入字符

012

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

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

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

終止狀態

q30{q。}{q3}

解答:

狀態說明狀態輸入字符

012

起先狀態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]

終止狀態[q2,q3][q2,q3][qO]fq2,q3]

終止狀態[ql,q2,q3][q2,q3][q0,ql,q21[ql,q2,q3]

[q0,ql,q2]

[ql,q314j2

,2-J。Iq3,ql,q2]

2/Pl時。必工^

1

圖3-10所示NFA等價的DFA

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

12.證明對于隨意的NFA,存在與之等價的NFA,該NFA最多只有一個終止狀態

(劉鉉02282083)

證明：對于隨意的NFAM=(Q,Z,5,q(),F),我們假如能構造出一個只有一個終止狀

態的NFA,并且與之等價，即可證明上面的定理

而對于隨意的NFA存在下面兩種狀況：

(1)終止狀態只有一個

(2)終止狀態有多個

要構造這個等價的NFA,可以采納如下方法：

對(1)無需變更，該NFA即為滿意條件的NFA

對(2)可以在該NFA的狀態圖上添加一個新的終止狀態，并將原來的多個終止狀態所連接的

弧復制到該狀態，，此時這個終止狀態為新狀態圖中唯一的終止狀態，且這個新的NFA與

原NFA等價，滿意條件

我們總能構造出這樣的NFA

因此對于隨意的NFA,存在與之等價的NFA,該NFA最多只有一個終止狀態

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

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

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

注：轉化成相應的DFA進行處理，然后可參考第8題的思路

證明:（周期律02282067）

首先構造一個與NFA等價的DFA，歷3依據定理3.?（P106）,L（M、）=

構造％=@，工兩[如，入），其中

。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]

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

即取全部確定化后不是終結狀態的狀態為M2的終結狀態。

為了證明〃"2）=2*一"加3），我們在％的基礎上=（。4，￡必先,已），其

中。4=。3，久=&，吊二。4，即全部M確定化后的狀態都為終結狀態。明顯

L（〃4）=Z*，

VxeL（M2\貝IJ次外,幻0鳥工。=＞方（%,1）。工工。=/任〃/3），又因為

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

故〃/2）q2*一（%）

同理簡單證明〃加2）3Z?一^^3）

故〃加2）=2*—〃加3），又因為L（“3）=L（M]），故〃"2）=Z"—"MJ

可知，構造的是符合要求的。

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

14.構造識別下列語言的￡-卬人。（吳賢培02282047）

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

個字符是1,且以01結尾鼠

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

0,I

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

符是1,且以01結尾}

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

S

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

結尾}。

解：關鍵是構造第一個FA,方法是設置5個狀態：

qo：表示起先狀態，以及連續出現了兩個以上的。時所進入的狀態。

q1：表示q0狀態下接受到1時（即起先狀態或2個以上的0后輸入1時）所進入

的狀態。

q＞：表示卬狀態下接受到0時（即起先狀態或2個以上的0后輸入10時）所進入

的狀態。

q；,：表示qz狀態下接受到1時（即起先狀態或2個以上的0后輸入101時）所進入

的狀態。

qi：表示q?狀態下接受到1時（即起先狀態或2個以上的0后輸入1011時）所進

入的狀態。

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

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

子串}。

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

0.I0,I

另外，本題可以構造DFA如下（其中5為陷阱狀態）:

0

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

串}。

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

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

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

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

15.(I)依據NFAM3的狀態轉移函數，起始狀態qo的閉包為-CLOSURE(q0)={qoq?}。

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

狀態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}，因為q3為終止狀態,所以q2={qo.qi.qz.q3}

為終止狀態

（2）又上述方法得

狀態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}因為各狀態均含

有終止狀態，所以qo,qi，q?.q3.q4均為終止狀態

注：本題沒有必要依據NFA到DFA轉化的方法來做，而且從-NFA到NFA轉化時狀態沒有

必要變更，可以完全采納-NFA中的狀態

如（1）

狀態01

q。（起先狀態）{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（終止狀態）

⑵

狀態01

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

qi{q2}{qi.qz)

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

q3（終止狀態）空(qo)

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

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

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

證明：不妨設Qi與Q2的交集為空

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

1)E=E|UE2F=F|UF2

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

e

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

(3)證明：

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

設x￡L(MI)UL(M2)，從而有x￡L(MD或者xeL(M2),當x￡L(M?時

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)

同理可證當x￡L(M2)時x￡L(M)

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

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

設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)因為Qi與Q2的交集為空而且3(q°,x)WFF=FIUF2則

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

假如是6(q*x)因為Qi與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證明：對于隨意的FAM]=(0],Z[b],40[,耳),~4用2=(。2，工2?2國02，工)，

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

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

1)對VqWQHfi},aGLU{￡}

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

2)對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在處理的過程中，經過的狀態全部都題沖的狀態，所以在定義

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

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

例2在處理々的過程中,經過的狀態全部都她22中的狀態,所以在定義

M時，對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)再證明

設xwL(M),即

bQi.x)—

由于M是從外?啟動的，由M的定義可知M要達到狀凝，必須

先到/；由于除了對應狀態轉腐I數式/九￡)=@2}的移動

外，不存在對出發的任何其他移動而且該移動蹤的必經

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

將M從狀態如引導到狀態九G將M從狀態強引導到狀態

.即

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

=^(/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.證明：對于任意的FAM尸（Q1Zeq。』），FAM2=（Q2N血,q02月）

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

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

F

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

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

（1）設：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）設：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卜

又因為FA和DFA具有等價性，所以原命題得證。

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

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

本章學習了DFA,NFA,e-NFA,2DFA和2NFA

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

最大的區分就是狀態轉移函數6

對于DFA,字母表中的每個字母都有唯一確定的狀態轉移函數。也就是說V8（q,a）eQ

XX,q￡Q,aWE只有哇一確定的狀態。

對于NFA,對于字母表中的每個輸入字符可以有不同的狀態轉移，對于￡串，是一個到自

身的移動。

對于￡?NFA,是指在不接受任何字符的狀況下，自動機的狀態可以發身轉移。

對于2DFA,對于字母表中的每個字符，對于每個狀態都有唯一的狀態轉移，即V5（q,a）

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

狀態轉移中不移動，或者回退一個，或者向下讀一個。

對于2NFA,與2DFA相像，但是并不是對于字母表中的每個輸入字符都有轉移函數，2NFA

與2DFA的區分類似于DFA與NFA的區分。