形式语言与自动机理论-蒋宗礼-第三章参考答案

第三章作业答案

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的区分。