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

第三章作业答案

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

(1)请分别给出它们在处理字符串1011001的过程中经过的状

态序列。

(2)请给出它们的形式描述。

图3—18两个不同的DFA

解答：(1)M1在处理1011001的过程中经过的状态序列为

q0q3qlq3q2q3qlq3;

M2在处理1011001的过程中经过的状态序列为

q0q2q3qlq3q2q3ql;

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

用图上作业法把它们用正则表达式来描述:

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.构造下列语言的DFA(xx02282085)

(1){0,1}*

(2){0,1}+

S——KOA-(^>^C1

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

(设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态)

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

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

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

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

(设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态)

(7){x|x{0,1}+且当把x看成二进制时，x模5和3同余，要求当

x为0时,|x|=1,且x0时，x的首字符为1}

1.以0开头的串不被接受，故设置陷阱状态，当DFA在启动状态读

入的符号为0,则进入陷阱状态

(10){x|x{0,1}+且XXX至少含有两个1}

(11){x|x{0,1}+且如果x以1结尾，则它的XX为偶数；如果x以

0结尾，则它的xx为奇数}

可将{0,1}+的字符串分为4个等价类。

q0：［］的等价类，对应的状态为终止状态

ql:x的xx为奇且以0结尾的等价类

q2：x的xx为奇且以1结尾的等价类

q3：x的xx为偶且以0结尾的等价类

q4:x的xx为偶且以1结尾的等价类

（12）{x|x是十进制非负数}

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看成二进制数时,x%5=1}

Set(q2)={x|x+,并且把x看成二进制数时,x%5=2}

Set(q3)={x|x+,并且把x看成二进制数时,x%5=3}

Set(q4)={x|x+,并且把x看成二进制数时，x%5=4}

Set(q0)={x|x+,并且把x看成二进制数时，x%5二0并且x

不为0}

(8)

M={Q,,,qO,F)

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

={0,1}

当0<=i<=8时侯，

(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的第十个字符是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开头以0结尾}

Set(q2)={x|x+,并且x以0开头以1结尾}

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

Set(q2)={x|x+,并且x至少有俩个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结尾，xx为奇数｝

Set(q2)={xX+,以1结尾，XX为偶数｝

Set(q3)=(xx+,以0结尾，xx为偶数｝

Set(q4)={xx+,以1结尾，xx为奇数｝

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

Set(q3)={十进制非负整数后面接个小数点.}

Set(q4)=｛十进制正小数｝

(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,状态采用的形式，它比较清楚地表达出该状态所对

应的记忆内容，给我们解决此问题带来了很大的方便，我们是否

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

从此问题的讨论，你能总结出什么来？(xxxx02282084)

答：我认为能够直接用代替，因为在例3-6xx,只是一种新的表示方

法，用来表示状态存储的字符，这样就省去了在xx逐一给出每

一个具体的输入字符和状态的定义。它的作用在于使FAxx状态

定义更加简洁c

得到结论：在今后描述FA时，应该根据具体的情况，使用适

当的方法。

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.试区别FA中的陷阱状态和不可达状态。（xx贤培02282047）

解：（D陷阱状态（课本97页）：指在其它状态下发现输入串不可能

是该FA所识别的句子时所进入的状态。FA一旦进入该状态,

就无法离开，并在此状态下，读完输入串中剩余的字符。

⑵不可达状态（课本108页）：指从FA的开始状态出发，不可能到

达的状态。就FA的状态转移图来说，就是不存在从开始状态

对应的顶点出发，到达该状态对应顶点的路径。

⑶从两者的定义可见：相对于不可达状态来说，陷阱状态是可达的。

但是，它们都是状态转移图中的非正常状态。如果从状态转

移图中的状态引一条弧到不可达状态，同时不可达状态所有

的移动都是到自身。这样，不可达状态就变成了陷阱状态。

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>

注：此题目有问题，可以将题设改为：xxxO和1个数相等且交替出

现

6.证明：题目有不严密之处，图xx给出EFA与题目xx的语言L(M)

二{x|xx{0,1}+且xxxO的个数和1的个数相等}不完全对应,首

先图xx的DFA可接受空字符串，而L(M)不接受，其次，对于

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

(1)根据图中的DFA可看出，右下角的状态为陷阱状态，所

以去除陷阱状态

(2)由DFA可构造出与其对应的右线性文法：(xx02282083)

S—0A

Af1S|1

STTB

8-()S|0

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

Sf01S|01

Sf105|10

由此可以看出该文法接受的语言为L={(10|01)*},显然01或10

分别是作为整体出现的，所以L(M)xxO和1的个数相等。

VX

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

*4*

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

7.设DFAM=,证明：对于

注：采用归纳证明的思路

证明：(周期律02282067)

首先对y归纳，对任意x来说，|y|二。时，即y二

根据DFA定义，故原式成立。

当|y|二n时，假设原式成立，故当|y|=n+l时，

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

根据DFA定义，故

原式成立，

同理可证，对任意的y来说，结论也是成立的。

综上所述，原式得证

Klx、］,

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

KI>KI>«,

8.证明：对于任意的DFAM1=(Q,2,6,q0,Fl)存在DFA

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

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

证明：(1)构造M2。

设DFAM1=(Q,S,8,q0,Fl)取DFAM2=(Q,2,8,q0,Q—Fl)

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

对任意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.对于任意的DFAMl二(QI,£,31,q01,Fl),请构造DFA

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

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

(1)构造E-NFAM使得L(M)=L(M1)取£-NFAM=(Q,E,6,

q0,{qOl})其中：

1)Q=QIU{q0},qOQI

2)对于q,p£Ql,a£X,如果81(q,a)=p,q£6(p,a)

3)6(qO,£)二Fl

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

对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)

同理可证对于x=a2…am^L(Ml)xT=am

am-l••,alEL(Ml)

以田二口皿丹得证

(3)将£-NFAM确定化

首先构造与£-NFAM=(Q,S,6,qO,{qOl})等价的NFA

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

其中对于(q,a)62(q,a)=6(q,a)

然后按照以前学过的方法构造与NFAM3=(Q,E,52,qO,(qOl})

等价的DFA

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

6l([ql,q2,•••,qn],a)=[pl,p2,—,pn]当且仅当

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所做完全一样！！

10、构造识别下列语言的NFA(xx02282091)

(1){1,£{0』}’.目时不含形勿100的子串}

1

___r--■-

,■

1

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

―

0.।_,°

一7~I4

£

(1.1

⑶{小€{0,1}+.目时不含形如10110的子串}

!——O-^->©---------------H——

0.I°

0.I

(4){AXG{0,1}+和地勺倒数第10个字符是1,且以01结尾}

0.I

(5){x|xe{O,l}+且似0开头以1结尾}

(6){x|xe{0Jf至少含有两个1}

o.1

0.I

(7){]k£{0,1}'且如果,似1结尾，则它的长度为偶数;

如果以0结尾，则它的长度为奇数}

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

0.I

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

0.1

0.1

这是最基本的单元，其他的可以通过这个逐级构造出来，以满足

题目要求。

************************1],根据给定的NFA,构造与之等价的DFA.

(xx02282090)

(1)NFAMl的状态转移函数如表3-9

状态说明状态输入字符

012

开始状态qo{qO,ql)fq0,q2){q0,q2|

ql{q3,qO)0{q2}

q20{q3,ql}{q2,ql}

终止状态q3{q3,q2}{q3}{q0}

解答:

状态说明状态输入字符

012

开始状态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]

终止状态[qO,ql,q3][q0,qhq2,q3][qO,q2,q3][qO,ql,q2]

终止状态[q0,q2,q3][q0,ql,q2,q3][qO,ql,q2,q3jIqO,q2|

终止状态[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等价的DFA

(2)NFAM2的状态转移函数如表3T0

状态说明状态输入字符

012

开始状态q0{ql，q3}{ql}{q0}

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

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

终止状态q3{q。}{q3}

0

解答:

状态说明状态输入字符

012

开始状态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]

终止状态[q2,q3][q2,q3][qO]Iq2,q3]

终止状态[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等价的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.证明对于任意的NFA,存在与之等价的NFA,该NFA最多只有

一个终止状态

(xx02282083)

证明：对于任意的NFAM=(Q,£,6,q0,F),我们如果能构

造出一个只有一个终止状态的NFA,并且与之等价，即可证明上面的

定理

而对于任意的NFA存在下面两种情况：

(1)终止状态只有一个

(2)终止状态有多个

要构造这个等价的NFA,可以采用如下方法：

对(1)无需变化，该NFA即为满足条件的NFA

对⑵可以在该NFA的状态图上添加一个新的终止状态，并将原

来的多个终止状态所连接的弧复制到该状态上，此时这个终止状态为

新状态图中唯一的终止状态，且这个新的NFA与原NFA等价，满足

条件

我们总能构造出这样的NFA

因此对于任意的NFA,存在与之等价的NFA,该NFA最多只有一个

终止状态

*>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.试给出一个构造方法，对于任意的NFA，构造NFA，使得

注：转化成相应的DFA进行处理，然后可参考第8题的思路

证明：（周期律02282067）

首先构造一个与NFA等价的DFA,根据定理3.1（P106）,

构造其中

，〃，

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

）（（

国（[%•••%]，4=[p-Pm]<=>d{%..4},〃）=Pi:.Pm}

在此基础上，

即取所有碓定化后不是终结状态的状态为的终结状态。

为了证明，我们在的基础上，其中，即所有确定化后的状态

都为终结状态。显然

则又因为故，故

同理容易证明

故，又因为，故

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

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.构造识别下列语言的£-NFAo(XX贤培02282047)

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

和x的倒数第10个字符是1,且以01结尾}。

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

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

和x的倒数第10个字符是1,且以01结尾}

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

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

串}U{x|x£{0,1}+且x以0开头以1结尾}。

解：关键是构造第一个FA,方法是设置5个状态：

q0：表示开始状态，以及连续出现了两个以上的0时所进入

的状态。

ql：表示q0状态下接受到1时（即开始状态或2个以上的0

后输入1时）所进入的状态。

q2：表示ql状态下接受到。时（即开始状态或2个以上的0

后输入10时）所进入的状态。

q3：表示q2状态下接受到1时（即开始状态或2个以上的0

后输入101时）所进入的状态。

q4:表示q3状态下接受到1时（即开始状态或2个以上的0

后输入1011时）所进入的状态。

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

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

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

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

另外，本题可以构造DFA如下(其中qt为陷阱状态)：

0

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

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

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

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

另外，本题可以构造DFA如下（其中q+为陷阱状态）：

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)根据NFAM3的状态转移函数，起始状态qO的闭包为

-CLOSURE(qO)={q0,q2}。由此对以后每输入一个字符后得到的新

状态再做闭包，得到下表：(xx02282085)

状态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为终止状态，所以q2={qO,ql,q2,q3}为终止状态

(2)又上述方法得

状态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}因为各状态均含有终止状态，所以qO,ql,

q2,q3,q4均为终止状态

注：本题没有必要按照NFA到DFA转化的方法来做，而且从-NFA

到NFA转化时状态没有必要改变，可以完全采用-NFA中的状态

如（1）

状态01

q。（开始状态）{qo.qi.q?qs){Qo.qi.q?,Qa}

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

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

q3（终止状态）{Qo,Qi,q?,P3){qo.qi,q2,qal

⑵

状态01

qo（开始状态）{qiqjqa,1{qo.qi,q?,q3)

{q2}(qi.q?)

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

q3（终止状态）空{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.证明对于的FAM1=(Q1,El,5l,q01,Fl),FA

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

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

证明：不妨设QI与Q2的交集为空

(1)构造M=(Q1UQ2U{q0},Z,b,qO,F)其中：

1)S=S1US=F1UF2

2)8(q0,£)={qOl,q02)对于q£Ql,aW£16(q,

a)=61(q,a)

对于q£Q2,a0Z2,6(q,a)=82(q,a)

(3)证明：

1)首先证L(M1)UL(M2)£L(M)

设xeL(Ml)UL(M2),从而有x£L(M1)或者xEL(M2),

当xWL(M1)时

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)

同理可证当xL(M2)时x£L(M)

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

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

设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)因为QI与Q2的交集为空而且6(qO,x)

eFF=F1UF2则

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

如果是§(q02,x)因为QI与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