形式语言与自动机理论-蒋宗礼答案

第三章作业答案

1已知DFAMl与M2如图3-18所示。(敖雪峰02282068)

(1)请分别给出它们在处理字符串iniinni的；什坦比归;力的弁太保利

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

0

07

图3-18两个不同的DFA

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

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

qyzqmqiqyqzqaqi:

⑵考虑到用形式语言表示，用自然语言似乎不是君弦容易，所以用

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

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

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

才*力**才*才*才才*才*♦，才，才*才**•才，才*才**#*#，#*才*力才力才“*

2.构造下列语言的DFA(陶文靖02282085)

(1){0，1}

⑵{0,1}

⑶（x|x｛0,1｝且x中不含00的串｝

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

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

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

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

A卜且中不含形如的子串}

(6){x|x{0f1x10110

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

(7){x|x{0,1卜且当把x看成二进制时，x模5和3同余，要求当x为。时，冈=1,且x=0时，x的首字符为1}

1.以0开头的串不被接受，故设置陷阱状态，当DFA在启动状态读入的符号为0,则进

入陷阱状态

设置个状态：开始状态除以余的等价类，除以余的等价类口除以

2.7qs,q-505125

余2的等价类，q3：除以5余3的等价类，q-除以5余4的等价类，接受状态qt

3.状态转移表为

状态01

qoqiqz

qiq3q2

qzqoq4

q3q】q2

qs1.q28

(8){x|x{0,1卜且x的第十个字符为1}

0,进入陷阱状态)

0.1

HXHKbd^

(设置一个陷阱状态，一旦发现X的第十个字符为

(9){x|x•{0,1}•且x以0开头以1结尾}

(设置陷阱状态，当第一个字符为1时，进入陷阱状态)

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

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

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

qo：［］的等价类，对应的状态为终止状态q.：x的长度为奇且以qz：X的长

度为奇且以q3：x的长度为偶巨以

q，：x的长度为偶且以1结僦睇类

(12){x|x是十进制非负数}

0.1,2.3,4.

5.6.7,8,9

(13)门

s-OO

(14)£

s―

3(1)(张友坤02282061)

'={0,1}

Set(q0)={x|x--)

(2)

'={0,1}

Set(q0)=;

Set(ql)-{x|

(3)

Set(q0)=;

Set(ql)={x|x-•并且x中不含形如00的子串｝

Set(q2)={x|x・，•并且x中不含形如nn的彳中\

⑷

=(041

Set(q0)=｛x|x匚•并且x中不含形如00的子串｝

Set(ql)=仅|x-,并且x中不含形如on的早中\

n

'={0,1)**

Set(q0)={x|「，并且x70}或者x中含形如100的子串}

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

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

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

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

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

'={0,1}

Set(q0)={;}

一+

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

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

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

'={0,1}

Set(qs)={}

Set(qe)={0}

Set(ql)={x|x,'+,并且ISx看成二进制数时，x%5=1}

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

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

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

Set(qO)={x|x三7♦，并且把X看成二进制数时，x%5=0并且x不为0}

(8)

M={Q.,，qo,F)

Q={qo.qi.qa,••・qo}

'={0,1}

当0<=i<=8时候，

、(qi,0)=、•(qi,l)=q(i+i)

(q9,l)=qio

：(q10,0)=[(qio,l)=qio

F={q10}

Set(qO)={;}

Set(ql)={0,1}

Set(q2)={x|X,AMf-»・、，.f、

Set(q3)={x|Xmia、、

Set(q4)={x|X'♦,并且凶=4}

Set(q5)={x|X7・,,并且|x|=5)

Set(q6)={x|X-*4-.\/./＞、

Set(q7)={x|x、♦,并且|x|=7)

Set(q8)={x|X•♦,并且|x|=8)

Set(q9)={x|Xfl11***

Set(ql0)={x•，并且X的第十个字符是・

lx1)

(9)M={Q,7,、，qo,F}

Q={qo,qi,q2}

、={0.1}

、(qo,O)=qi

、(qi,0)=qi

、(qi,l)=Q2

-(q2,1)=q2

、(q2,0)=qi

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,qi,q2}

={0,1}

-(qo,0)=qo

-(qo,l)=qi

、(qi,0)=qi

、(qi,l)=q2

、(q2fl)=qz

、.(q2,0)=q2

F={q2}

Set(qO)={0}*

Set(ql)={x|x-♦,并且x中只有一个1}

Set(q2)={x|x-♦,并且x至少有俩个1}

(IDM={Q,',、・，q°,F}

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

'={0,1}

、(qo,0)=q】

、(qo,l)=q4

、(qi,0)=q3

、(qi,l)=q2

-(q2,1)=q4

、(q2,0)=qi

-(q3,0)=qi

■(q3,1)=q4

、(q4,1)=q2

-(q4,0)=q3

F=(qo,qi,q2}

Set(q0)={;}

Set(ql)={xIx,v•，以。纭尾，长度为奇数

L以1结尾，长度为偶数

Set(q2)={x|

+,以0结尾，长度为偶数x・•以1

Set(q3)={x|

结尾，长度为奇数

(12)

M={Q,二、，qo,F)

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

'={,0,1,2,…⑼

F={ql,q2,q4}

-(qo,O)=ql

-(qo,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(qO)=｛;｝

Set(ql)=｛0｝

Set(q2)=｛十进制正整数｝

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

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

(13)

Set(qO)={;}

Set(qO)=-

(14)

Set(qO)={;}

4在例3-6中，状态采用qlAaz-an］的形式，它比较清楚地表达出该状态所对应的记忆内

容，给我们解决此问题带来了很大的方便，我们是否可以直接用品2.鸟1代替

q［a.a2...an］呢？如果能，为什么？如果不能，又是为什么？从此问题的讨论，你能总

结出什么来?(唐明珠02282084)

答：我认为能够直接用［a-a2...an］代替q［a-ia2...an］,因为在例3-6中,qlaQ，..®］只是

种新的表示方法，用来表示状态存储的字符，这样就省去了在：中逐一给出每一个具体的输入字符和状态的定

义。它的作用在于使FA中状态定义更加简洁。

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

5.试区别FA中的陷阱状态和不可达状态。

(吴贤培02282047)

解：⑴陷阱状态(课本97页)：指在其它状态下发现输入串不可能是该FA所识别的句子

时所进入的状态.FA一旦进入该状态，就无法离开，并在此状态下，读完输入串中剩余的字符。

⑵不可达状态(课本108页):指从FA的开始状态出发，不可能到达的状态。就FA

的状态转移图来说，就是不存在从开始状态对应的顶点出发，到达该状态对应顶点的路径。

⑶从两者的定义可见：相对于不可达状态来说，陷阱状态是可达的。但是，它们都是状态转移图中的非正常状

态。如果从状态转移图中的状态引一条弧到不可达状态，同时不可达状态所有的移动都是到自身。这样，不

可达状态就变成了陷阱状态.

♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦

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

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

={x|xx,{0,1卜且X

中0的个数和1的个数相等}不完全对应，首先图中的DFA可接受空字符串，而L(M)

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

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

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

(刘汪02282083)

S>0A

A>1S|1

S>IB

B>OS|0

将1S,1代入S>OA;06,代入SB得

S>0IS|01

S>1OS110

由此可以看出该文法接受的语言为L={(10|01)*},显然01或10分别是作为整体出现的，

所以L(M)中。和1的个数相等。

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

7•设DFAM=(Q.........q°,F),证明：对于-X,y-二*,qQ、.(q,xy)=、.C(q,x),y)

注：采用归纳证明的思路

证明：(周期律02282067)

首先对y归纳，对任意x来说，|y|=0时，即y=;

根据DFA定义、(q,;)Zq,.(q,xy)=、(q,x)=、.(、.(q,x),;)=、(、(q,x),y),故原式

成立。

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

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

根据DFA定义、(q,xa)二、.(、.(q,x),a),a',故

、(q,xy)二、(q,xwa)二、((q,xw),a)二、(((q,x),w)⑶二、(、(q,x),wa)二G(q,x),y)

原式成立，

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

综上所述，原式得证

****************************************************************^**************

&证明:对于任意的DFAMi=(QQ,S,q・H)存在DFAM2=(QQ,S,q・,F2),(冯蕊02282075)使得L(M2)=工一L(Mi)o

证明：m构造M2.

设DFAMi=(Q,I,S,qo,Fi)取DFAM2=(Q,工,S,qo.Q—Fi)

(2)证明L(M2)=Z—L(Mi)

对任意x•工'

x-L(M2)=1—L(Mi)：=S(q,x)Q—FAS(q,x):二Q并且S(q,x)'Fi二x：=I♦并且x-L(Mi)=x,工

♦——L(Mi)

****************************************************************^**************

9.对于任意的DFAMi=(Qi,刀,Si,qoi,Fi),请构造DFAMI=(Q2,刀,S碎2尸2),使得

L(Mi)=L(M2)\其中L(M)T={X|XT€L(M))(褚颖娜02282072)

⑴构造S-NFAM使得L(M)=L(M1)取「NFAM=(Q,刀,S,q-,{q。1})其中：

1)Q=QiU{q.},q.Qi

2)对于-q,p€Qi,a€E,如果Si(q,a)=p,q€S(p,a)

3)S(qo,e)=Fi

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

对-x=aia2…am€L(M)

qoaia2...am卜qfaiaz…am卜aiqia2...am卜aiazq2…am卜aia2...qm-iam

卜3i32...3mqoi

其中qf€S(qo,£),qi”叫ai).q2，，％a2),am)并且qf“i

贝USi(qo.,am)=qm-i,Sami)=qm-2,...Si(q2,a2)=qiSi(qi,ai)=qf

因此qoiam8m-i•...ai卜qm-iam-i«...ai卜4m3m-i...C|2323i卜am-i...22C]i3i

卜am8m-i...32aiqf

因此amam-i...ai€L(Mi)即xT€L(Mi)

同理可证对于-x=aia2...am€L(Mi)xT=a(nam-i..ai€L(Mi)

L(M)=L(M》得证

(3)将e-NFAM确定化

首先构造与e-NFAM=(Q,刀,S,qOj{qa})等价的NFAM3=(Q刀,S2,qOf{qoi})其中对于一(q,a)€Q*刀S

2(q,a)=S(q,a)

然后按照以前学过的方法构造与NFAM3=(Q,E,S2,qo,{q°i})等价的DFA

Mi=(Qi,E,Si,[q可,Fi)其中：Qi=2QFi.{q°i}

si([qi,q2.......qn],a)=(p卬2,…,pn]当且仅当S2({qi.q2，…，qn},a)={p卬2，…,pn}

注：此题(i。题)张友坤、吴玉涵所做完全一样！！

i。、构造识别下列语言的NFA(吴玉涵0228209。

(i)仅x€{0,i}+且x中不含形如00的子串}

i

⑵{XX-{0,1}且x中含形如10110的子串}

0.1

(3){xxA{0,l}+且x中不含形如10110的子串}

~~

(4)(x八。1八和x的倒数第10个字符是L且以01结尾}

0,1

—10Alo

(5){x乂人。1}+且x以0开头以1结

(6){xx人{0,1}+且x中至少含有两个1}

(7){xx70,1卜且如果x以1结尾，则它的长度为偶数;

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

1

s

(8){xx八{0,1}+且X的首字符和尾字符相等}

0.1

(9){XCOXTxJk{0,l}l

0,1

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

*************************n***m*mmmmm★★★★★★★★★★★★★★★★★

1L根据给定的NFA,构造与之等价的DFA.(吴丹02282090)

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

状态说明状态输入字符

012

开始状态q0{qO.ql){qO,q2}{qO,q2)

qi{q3,qO}0{q2}

q20{q3,ql}{q2,ql)

终止状态q3(q3,q2)(q3)(qO}

解答：

状态说明输入字符

012

开始状态

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

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

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

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

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

终止状态

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

终止状态

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

[qO,ql][qo,qi,q3]Iq0,q2,q3]

qO1

-一

1,20-1

o?0

0,1

1,2c

[qOzql,q2;q3]

2

[q0,qi,q2]2

-2

图3-9所示NFA等价的DFA

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

状态说明状态输入字符

012

开始状态qO{ql.q3){ql}{qO}

qi{q2}{ql,q2}(ql)

q2{q3,q2}{qO}{q2}

终止状态

q30(qO){q3}

解答:

状态说明输入字符

012

开始状态q0[ql,q3][ql][qO]

[qlq3][q2](q0,ql,q2][ql.q3]

[ql][q2][ql,q2][ql]

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

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

[qlq2][q2,q3][q0,ql,q2][qLq2]

终止状态[q2.q3][qZq3][qO][q2,q3]

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

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

iqia2.2

002

qO

吆仁］

[ql]

图3-10所示NFA等价的DFA

**************************ik******************************************r******

12.证明对于任意的NFA,存在与之等价的NFA,该NFA最多只有一个终止状态

(刘锂02282083)证明：对于任意的

NFAM=(Q,刀，3,qO,F),我们如果能构造出一个只有一个终止状态的NFA,并且与之等价，即可证明上面的定理

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

⑴终止状态只有一个

⑵终止状态有多个

要构造这个等价的NFA,可以采用如下方法：对⑴无需变化,该NFA即为满足条件的NFA对⑵可以在该NFA的状态图上添加

一个新的终止状态，并将原来的多个终止状态所连接的弧复制到该状态上，此时这个终止状态为新状态图中唯一的终止状态，

且这个新的NFA与

原NFA等价，满足条件我们总能构造出这样的NFA

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

13试给出一个构造方法，对于任意的NFAMi=(Qi/V/r,qo,Fi)构造NFA

M2=(QzF,2,qo,F2),使得L(Mz)八...-L(MJ

证明：(周期律02282067)

首先构造一个与NFAM,等价的DFA,Wk根据定理3.1(P136),L(M3)=L(MJ

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

构造M3=(Q\式q・],FJ其中

Q3=2QI,F3={[Pl/P2...Pm]|{pi,P2...Pm}Q,{Pi,Pz-Pm}Fi=},{»,P2...Pm}Q,3'

、3([qi...qn],a)二旧...Pm]=、i({q...qn},a)二{Pi...Pm}

在此基础上M2,Q2=QJ2.-3,F2={[Pi...Pm]|[P(...Prn]F3二}

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

为了证明L(M»二a*-L(M3),我们在M3的基础上M4=(Q4,',4,q0,F4),其

中Q|二Q3,、：4=,F4=Q4,即所有M,确定化后的状态都为终结状态。显然

L(M。八，，

・XL(M2),则、(q°,x)F2'-'=(qo,x)F3r=x'L(M3),又因为

(qo,x)Q3二'(q，,x)二、(q)x)L(M4、,故x.*-L(M3),

故L(M2)---LM)

同理容易证明L(M2)=7--L(M3)

★★

故L(M2)=^-L(M3),又因为L(M3)=L(MJ,故L(M?)-L(M,)

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

i4.构造识别下列语言的&-NFA。(吴贤瑁02282047)

(1){x|x€{0,i}+且x中含形如iOiiO的子串}U{x|x€{0,i},和>:的倒数第i0

个字符是i,且以5结尾}。

解：得到的「NFA如下所示：

0.1

（2）{x|x€{0,1}•且X中含形如10110的子串}{XIx€{0.1}•和X的倒数第10个字符是1,且以01结尾}

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

（3）{x|x£{0,1}•且x中不含形如10110的子串}U{x|x€{0,1}-且x以0开头以1结尾}°

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

q。：表示开始状态上以及连续出现了两个以上的_0时所进入的状态。

qi表示q.状态下接受到1时（即开始状态或2个以上的0后输入1时）所进入的状态。

q2

：表示中状态下凌受到0时（即开始状念或2个以上的0后输入10时）所进入的状念.

q?

：表示q，状态下凌受到1时（即开始状态或2个以上的0后输入101时）所进入的状态。

中：

表示q；状态下接受到1时（即开始状态或2个以上的0后输入1011时）所进入的状态。

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

（4）{x|x€{0,1}•且x中不含形如00的子串}{xIx€{0,1}+且x中不含形如11的子串}0

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

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

（5）｛xI制。1｝+且x中不含形如00的子串｝A｛X串｝0x包0,1），且x中不含形如11的子

解：由于x中既不含形如00的子串，又不含形如

串。所以，得到的「NFA如下所示：11的子串，故x中只能是01相间的

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

15.⑴根据NFAM3的状态转移函数，起始状态qo的闭包为-CLOSURE（q，）=｛qo.q?｝。由此对以后每输入一

个字符后得到的新状态再做；闭包，得到下表：（陶文靖02282085]

状态01

{qo，q2}{qo.qi,q2){qo,qi,i2,Q3}

{qo,qL哈}{qo,qi-}{qo,qi,12,AS)

{qo,qi{qo.qi,{qo,qi,M2,M3}

qo={qo,q2},qi={qo,qi.q:},q2={qo,qi,qzqs},因为q3为终止状态,所以q2={qo,qi,qzq3)

为终止状态

qqiqz

（2）又上述方法得

状态01

{qi.q3){q3,。2}{q0.qi,«2,间

{q3,。2}{q3M{qo，q】，q3}

{q0,qi,Q2,Q3}{q1^2,03){q0,qi,吟,。3}

{qo,qi.03}{qLa「3}{q0.qi.qzq3}

{q1.«3}{q3,。2}{q0.qi.i2,叫}

qo={qi,q3},qi={q3,qz},q2={qo.qcqzq3},q3={qo,qiq3},q4={q1,q2,q3}因为各状态均含

有终止状态，所以qo,qi.qzq3,q，均为终止状态

注：本题没有必要按照N「A到D「A转化的方法来做，而且从-N「A到N「A转化时状态没有必要改变，可以完全

采用・NFA中的状态

如（1）

状态01

qo（开始状态）{q01q1.q2q3}{q。qiq2q3)

qi{q。q1.q2q3}{q1.q2q3}

qz{qaq1.q2q3){q1q2q3}

qs（终止状态）{q0q1,qzq»{qaq1,qzqj)

⑵

状态01

qo（开始状态）{qiqzq%}{qoqgq}

qi(q4{q1,Q2)

qz{7273}(qoq?q3}

qj（终止状态）空{qo)

16.证明对于一的FAMi-(QirEi,Si,qoi,F",FAMivQz刀2,3zq.Fz),存在FAM,

使得L(M)=L(M川L(M2)(褚颖娜02282072)

证明：不妨设Q】与Qz的交集为空

(1)构造M=(QiUQ2U{q.},刀,S,qo,F)其中:

1)刀=后1UE2F=FLUF2

2)S(qo,e)=14。1q。2}对于一口€(^3€£iS(q,a)=Si(q,a)

对于-q€Qza€E2,S(q,a)=S2(q,a)

⑶证明：

1)首先证L(Mi)UL(M2)€L(M)

设x€L(M.)1L(M2),从而有x€L(M。或者x€L(M2),当x€L(M1)时

Si(qoi,x)€Fi

由M的定义可得：

S(qo,x)=S(qo,ex)=S(S(qo,e),x)=S({qoi,qo2},x)=S(qoi,x)US(qo2,x)

=Si(qoi,x)US(qoifx)€FiUS(qoi,x)即x€L(M)

同王里可证当x€L(M2汨寸x€L(M)

故L(M1)UL(M2)€L(M)

2)再证明L(M)€L(M1)UL(M2)

设x€L(M)则S(qo,x)€F

由M的定义：

S(qo,x)=S(qo,ex)=S(S(qo,e),x)=S({qoi,qo2},x)=S(qoi,x)US(qo2,x)

如果是S(q。l,x)因为Ql与Q2的交集为空而且S(qo,x)€FF=FiUF2贝

S(qoi,x)=Si(qoi,>:)€Fi因此x€L(M1)

如果是S(q*x)因为Qi与Q2的交集为空而且S(qo,x)€FF=FiUF2贝

S(q02,x)=S2(qo2,>:)€Fi因此x€L(M2)

因此x€L(Mi)UL(M2)L(M)€L(M1)UL(M2)得证

因此L(M)=L(Mi)fL(M2)

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

(唐明珠02282084)

17证明：对于任意的FAMi=(Qi,t,诂,qn,FJ,FAM2=(Qz—2严2,q?F?),

存在FAM,使得L(M)=L(M])L(M».

证明：令M=(QiQ?r.rqoi,{f，}),其中S的定义为：

1)对一q€Qi-{f1},a€EU{e}

3(q,a)=3l(q,a);

2)对-q€Q2-{f2},a€EU{&}

3(q,刃=32(q,a);

3)3(fi,&)={C02}

要证L(M)~L(MJL(M2),

只需证明L(M儿(M?)二L(M),L(M儿(Mb)二L(M)

1.证明L(MI)L(M2)L(M)

设xL(Mi)L(M)从而有x「L(MJ并且x2L(M)

使得X=X1X2

M•，在处理搭的过程中,经过的状态全部都是01中的状态，所以在定义

M时，对-qQ「a:-二,、(q,x)=(q,a)

故、心。i,司二、】(q。］,X2)-{fj

M2在处理X2的过程中,经过的状态全部都是Q2中的状态，所以在定义

M时，对一qQ-a-二，、(q,x)二2(q,a)

(<102,X)=-2(q(n,X)-^f2>

下面证明L(M)

、(q%x)二、(q=i,XiX2)

=((qoi,Xi),X2)

Gi^oi-xi),x2)

-;(fVx2)

二(fl,X2)

二、(、(fC；W)

-”(qO2，X2)

=12^02.x2)

7)

即得证x-L(M)

2)再证明

L(M)L(M1)L(M?)

设xL(M),即

、(q・1,x)={f2}

由于M是从q。】启动的，由M的定义可知,M要达到状态fz必须先到

£由于除了对应状态转移函数式代〃={qo»的移动外,不存在从小出

发的任何其他移动，而且该移动是f2的必经移动，所以比存在X的前

缀X1和后缀力使得-XN,并且X1将M从状态q01引导到状态将M

从状态q02引导到状态f2即

、(q・i,x)二、©1,皿)

=S(f/2)

=,(%,冷)

=6(qx)

这表明

x[L(M0x2L(M?)

从而x=XjX2L(M：)L(M2：I

故L(M)L(M1)L(Mz)

综上所述，

L(M八L(M】)L(Mz

(吴丹02282090)

18•证明:对于任意的FAML(QJ,Z;,@qoi,),FAM2=(Qzg2,§2002,&)

存在FAM,使得LM=LMA|LMb。

证明：不妨将这些FA看成DFA

取乂=Q1Q2,C,r,qoi,qo?},F

对于-a:-工1T2,q,P卢Q,、q,p,a二dq,a,学p,a.

1设：xLM贝！Jx=xlx2.....xk其中xii(l,kL二pr2

使得'q,p,xi=Fq,xiA2P,xi

.xiLMiriLMzhXLMjILM，

从而可得LM一LMiDLM2

2设：xLMiITM2贝vx=xlx2……xk其中xii〔l,kL二I、

有Fq,xi且：中，xi从而使得

、iq,xiIqp,xi;2p,xi'q,p1