《形式语言与自动机理论-蒋宗礼-参考答案.doc》由会员分享，可在线阅读，更多相关《形式语言与自动机理论-蒋宗礼-参考答案.doc（50页珍藏版）》请在三一文库上搜索。
1、第三章作业答案1已知DFAM1与M2如图3- 18所示。(1) 请分别给出它们在处理字符串(2) 请给出它们的形式描述。(敖雪峰 02282068)1011001的过程中经过的状态序列。图3- 18两个不同的DFAqoq3qiq3q2q3qiq3；解答:(1)M1在处理1011001的过程屮经过的状态序列为M2在处理1011001的过程中经过的状态序列为q°q2q3qiq3q2q3qi；考虑到用形式语言表示，用自然语言似乎不是那么容易, 所以用图上作业法把它们用正则 表达式来描述M1: 01 +(00+1 )(11 +0)11 +(10+0)(11 +0)*M2: (01 + 1+0
2、00)(01 )*+(001 + 11)(01 + 1 +000)*(陶文嬪 02282085 )2. 构造下列语言的DFA(D 0, 1(3) x|x 0, 1但X中不含00的串(设置一个陷阱状态，一旦发现有 00的子串，就进入陷阱状态)(4) x|x 0 , 1沮x中不含00的串(可接受空字符串，所以初始状态也是接受状态)x|xA0, 1但x中不含形如10110的子串(设置一个陷阱状态，一旦发现有 00的子串，就进入陷阱状态)(7)x|x0, 1但当把x看成二进制时，x模5和3同余，要求当x为0时,|x|=1,_ax=0时,x的首字符为11.以0开头的串不被接受，故设置陷阱状态，当DFA在
3、启动状态读入的符号为0,则进入陷阱状态2.设置7个状态：开始状态qs,q。：除以5余0的等价类，除以5余1的等价类口 2：除以5 余2的等价类，q3：除以5余3的等价类，q4：除以5余4的等价类，接受状态qt3.状态转移表为状态01qoqiq2qiqaq2Q2qoq4q3qiq2q4q3q4(8) x|x0, 1但x的第十个字符为10,进入陷阱状态)(设置一个陷阱状态，一旦发现x的第十个字符为(9) x|x 0, 1且x以0开头以1结尾(设置陷阱状态，当第一个字符为1时，进入陷阱状态)(10) x|x 0, 1且x中至少含有两个10x以0结尾，则它的长度(11) x|x0, 1且如果x以1结尾
4、，则它的长度为偶数；如果 为奇数可将0,甘的字符串分为4个等价类。qo：的等价类，对应的状态为终止状态qi： x的长度为奇且以q2： x的长度为奇且以0结尾的等价类q3： x的长度为偶且 1结尾的等价类以0结尾的等价类q4： X的长度为偶且以1结尾的等价类(12)x|x是十进制非负数(13) ns OO(14) £(张友坤 02282061)3(1)0'0,1Set(q0)=x lx-5'0,1Set(q0)=；Set(q1)=x | x- - *(3)-=0,1Set(q0)=；Set(q1)=x并且x中不含形如Set(q2)=x |x-并且x中不含形如00的子串0
5、0的子串00的子串00的子串Set(q0)=x | x匚-*并且x中不含形如Set(q1)=x | x 并且x中不含形如*=0,1*Set(q0)= x|，并且"0或者x中含形如100的子串Set(q1)=x | x三*,并且x中含形如1的子串Set(q2)=x | x 二，并且x中含形如10的子串Set(q3)=x | xr,并且x中含形如101的子串Set(q4)=x| X-,并且x中含形如1011的子串Set(q5)=x| X-,并且x中含形如10110的子串'0,1Set(q0)= ； +Set(q1)=x | x0 Set(q2)=x | x-,并且x中不含形如10
6、110的子串而且x中含有1Set(q3)=x | X-,并且x中不含形如10110的子串而且x屮含有1(7)0=0,1 Set(qs)= Set(qe)= 0Set(q1)=x | x, '+,并且把x看成二进制数时，X% 5=1Set(q2)=x | X；，并且把x看成二进制数时，X% 5=2Set(q3)=x |Set(q4)=x |x 7 ,并且把x看成二进制数时，x% 5=3x三7 +,并且把x看成二进制数时，X% 5=4Set(q0)=x |(8)M=Q, *x三7 +,并且把x看成二进制数时，X% 5=0并且x不为0Q=q o,qi,q2, qo '=0,1当0&l
7、t;=i<=8时候，、(q i,0)=、( q i,1 )=q (i+i) (q9,1)=Q 10：(q io,O)=(q icJ)=q ioF= q 10Set(qO)= ； Set(q1)= 0,1Set(q2)=x |X，并且凶=2Set(q3)=x |X，并且|x|=3Set(q4)=x |X",并且凶=4Set(q5)=x |X7+,并且 |x|=5Set(q6)=x |X.，并且凶=6Set(q7)=x |X、 并且 |x|=7Set(q8)=x |X",并且 |x|=8Set(q9)=x |X 并且 |x|=9Set(q10)=x1 X并且x的1(9)
8、M=Q,7,、，q°,FQ=q o,qi,q2、=0,1、(q o,O)=qi、(q b0)=q 1、(q iJ)= Q2(q 2,1)= q2、(q 2,0)= qiF=q 2Set(q0)= ; Set(q1 )=x | x并L x以0丿-头以0结尾Set(q2)=x | x .，并且x以0开头以1结尾 (10) M=Q, r, qo.F Q=q o,qi,q2=0,1(q o,0)=qo(q o,1)=qi、(A i,0)= q 1、(q d)= Q2、(q 2,1)= q2、.(q 2,0)= q2F=q 2并且x中只有一个1 并且X至少有俩个1Set(qO)= 0*Set(
9、q1)=x | x -Set(q2)=x| x (11) M=Q, ',、，qo,FQ=q o,qi,q2, q3,q *=0,1、(q o,0)=qi、(q o,1)=q4、(q 1,0)= q 3、(A iJ)=Q2(q 2,1)= q4、(q 2,0)= qi(q 3,0)= qi(q 3,1)= q4、(q 4,1)= q2-(q 4,0)= qsF= q o ,q 1 ,q 2Set(q0)= ； Set(q1 )=x | x, v+,以0结尾，长度为奇数 j Set(q2)=x | ，以1结尾，长度为偶数Set(q3)=x |以0结尾，长度为偶数xSet(q4)=x |以1
10、结尾，长度为奇数(12)M=Q,',、，qo,FQ=q0,q1,q2,q3,q4*=.,0,1,2,9F=q1,q2,q4-(q o,O)=q1-(q o,1|2|3|4|5|6|7|8|9)=q2、(q b )=q2：(q 2,0|1|2|3|4|5|6|7|8|9)=q2、(q 2, . )=q3.(q 3,0|1|2|3|4|5|6|7|8|9)=q4f(q 4,0|1|2|3|4|5|6|7|8|9)=q4Set(q0)= ； Set(q1)=0Set(q2)=十进制正整数Set(q3)=十进制非负整数后面接个小数点.Set(q4)=十进制正小数(13)Set(qO)= ;Se
11、t(qO)=-(14)Set(qO)= :4在例36中，状态采用qlAaz-an的形式，它比较清楚地表达出该状态所对应的记忆内容，给我们解决此问题带来了很大的方便，我们是否可以直接用品2.鸟代替q a!a2.an呢？如果能，为什么？如果不能，又是为什么？从此问题的讨论，你能总结出什么来？（唐明珠02282084）答:我认为能够直接用a!a2.an代替q aia2an,因为在例36屮,qlaQ?.®只是种新的表示方法，用来表示状态存储的字符，这样就省去了在：中逐一给出每一个具体的输入字符和状 态的定义。它的作用在于使FA中状态定义更加简洁。得到结论：在今后描述FA时，应该根据具体的情况
12、，使用适当的方法。5. 试区别FA中的陷阱状态和不可达状态。（吴贤于君0228204刀解：（1）陷阱状态（课本97页）：指在其它状态下发现输入串不可能是该FA所识别的句子时所进入的状态。FA-旦进入该状态，就无法离开，并在此状态下，读完输入串中剩余的字符。不可达状态（课本108页）：指从FA的开始状态出发，不可能到达的状态。就FA的状态转移图来说，就是不存在从开始状态对应的顶点出发，到达该状态对应顶点的路径。（3）从两者的定义可见：相对于不可达状态来说，陷阱状态是可达的。但是，它们都是状态转移图屮的非 正常状态。如果从状态转移图屮的状态引一条弧到不可达状态，同时不可达状态所有的移动都是到 自身
13、。这样，不可达状态就变成了陷阱状态。注：此题目有问题，可以将题设改为：x中0和1个数相等且交替出现6. 证明：题目有不严密之处，图中给出DFA与题目中的语言L（M ） =x|x x, 0 , 1且 x中0的个数和1的个数相等不完全对应，首先图中的DFA可接受空字符串，而L （ M）不接受，其次，对于有些句子，例如1100, L （ M）可以接受，但DFA不接受（1）根据图屮的DFA可看出，右下角的状态为陷阱状态，所以去除陷阱状态（2）由DFA可构造出与其对应的右线性文法：（刘02282083 ）S>0AA> 1S | 1S> 1BB > OS | 0将代入S>OA
14、； 06,代入SB得S>01S|01S > 1 OS | 1 0由此可以看出该文法接受的语言为L=（10|01） *，显然01或10分别是作为整体出现的,所以L（M）中0和1的个数相等。7设 DFAM=（Q,、，、，q。，F）,证明：对于-X,y二 *,q Q,、.（q,xy） =、. C （q,x）, y）注：采用归纳证明的思路证明：（周期律02282067）首先对y归纳，对任意x来说，|y| = 0时，即y=；根据 DFA 定义、（q,；）二口八（q,xy）=、（q,x） =>.（>. （q, x）, ；）=、（、（q,x）, y）,故原式 成立。当|y| = n时
15、，假设原式成立，故当|y|=n+1时，不妨设 y = wa, |w| = n, |a| = 1根据 DFA 定义、（q , xa ）二、.（、.（q , x）, a）, a ',故、(q,xy)二、(q,xwa)二、(q,xw),a)二、(q,x), w),a)二、(、(q, x), wa)二 G (q, x), y)原式成立，同理可证，对任意的y来说，结论也是成立的。综上所述，原式得证& 证明:对于任意的 DFAMi=(QQ,S,qFi)存在 DFA M 2=(QQ , S ,q°,F2),(冯蕊 02282075)使得 L(M 2)=I 一 L ( MJ o证明：
16、(1)构造M2。设 DFAM 1=(Q,I,S ,qo,Fi)取 DFA M 2=(Q,工,S ,qo,Q Fi)(2)证明 L(M2)=工一L ( Mi)对任意x工*=工并且x -x- L(M 2)=工一L ( Mi) ： = S (q,x) Q FA S (q,x):二 Q 并且 S (q,x) 'Fi 二 x： L(M i)=x,工 一 L ( Mi)9. 对于任意的DFA Mi=(Qi,刀,S i,qoi,Fi)，请构造DFA Mg,刀,S 2牛尸2),使得L(M i)=L(M 2)To 其中 L(M)T=X|XT L(M)(褚颖娜 02282072)构造 s -NFA M 使
17、得 L(M)=L(M 1)取NFA M=( Q,刀,S , q。q o")其41) Q= QiU q° , q° * Qi2) 对于- q,p Qi,aE,如果 Si(q,a)=p,q S (p,a)3) S (q。, e )= Fi(2) 证明：L(M)=L(M i)T对- x=aia2-am L(M)qo ai a2 am 卜qfaia2am 卜a qia2am卜aia2 q2am 卜ai a2qm-i am卜 aa2 amqoi其中 qt S (qo, J, qi"% as), qsg, a2), qOism-i, am)并且 qz贝g S i(q
18、oi, am)= qm-i, S i(qm-i, am-i)= qm-2,*S i(q2, S2)= qiS i(qi, ai)= qf因止匕 Qoi am am-i ai 卜 am qm-i am-i.ai b am 3m-i -q2 S2 Si b am am-i-a2 qiSi卜 am am-i -a2 aiqf因此 am am-i ai L(M i)即 xT L(M i)同理可证对于 x=aia2-am L(M i) xT=am am-i ai L(M i)L(M)=L(M i)T 得证(3) 将e-NFA M确定化首先构造与 e-NFA M=( Q,刀,S , q°, q&
19、#176;i)等价的 NFA M 3=( Q,刀,S 2, q°, q°i)其中对于 一 (q,a)eCT 刀 S2(q,a)=SJ(q,a)然后按照以前学过的方法构造与NFA M 3=( Q, E ,S 2, q°, q°i)等价的DFAMi=(Qi,E,S i,qo,Fi)其中:Qi=2Q Fi= qoisi(qi,q2,，qn,a)=pi,p2,pn当且仅当 S2(q i,q2 ,，qn,a)= p i,p2,pn «*«*«*«*««*AA注：此题(io题)张友坤、吴玉涵所做完全一样！i
20、O、构造识别下列语言的NFA(吴玉涵02282091)(i) x x 0,i +且x中不含形如00的子串(2) X x0,1且x中含形如10110的子串(3) xxA0,1 +且x中不含形如10110的子串0. 10. 1(4) X A0,r和X的倒数第10个字符是X且以01结尾(5) x xA0,1 +且x以0开头以1结0, 101(6) x xA0,1 +且x中至少含有两个10. 10. 10. 1xxA0,1但如果x以1结尾，则它的长度为偶数；如果以0结尾，则它的长度为奇数1(8) xxA0,1+且X的首字符和尾字符相等0. 11(9) xcoxTx,/k0,11这是最基本的单元，其他的
21、可以通过这个逐级构造岀来，以满足题目要求。it*11.等价的DFA.根据给定的NFA,构造与之(吴丹 02282090)(1) NFAMi的状态转移函数如表3-9状态说明状态输入字符012开始状态qoqO,q1q0,q2q0,q2qiq3,q00q2q20q3,q1q2,q1终止状态q3q3,q2q3q0解答:状态说明状态输入字符012开始状态q0qO,q1q0,q2q0,q2qO,q1q0,q1,q3q0,q2q0,q2q0,q2qo,qiq0,q1,q2,q3q0,q1,q2q0,q1,q2q0,q1,q3q0,q1,q2,q3q0,q1,q2终止状态q0,q1,q3q0,q1,q2,q3
22、qO, q2,q3q0,q1,q2终止状态q0,q2,q3q0,q1,q2,q3q0,q1,q2,q3q0, q2终止状态q0,q1,q2,q3q0,q1,q2,q3q0,q1,q2,q3q0,q1,q2qO,q1 qo,qi,q3 q0,q2,q3101'22o0'11,2 厂、0,12 < ；q0,q1,q2,q3V q0,qi,q22" "1 _2图39所示NFA等价的DFANFAM2的状态转移函数如表3-10状态说明状态输入字符012开始状态q0qi,q3q1q0qiq2q1,q2q1q2q3,q2q0q2终止状态q30q0q3解答:状态说明状
23、态输入字符012开始状态q0qi,q3q1q0qi,q3q2q0,q1,q2qhq3q1q2qi,q2q1q2q2,q3qOq2q0,q1,q2q1,q2,q3qO, q1,q2q0,q1,q2q,q2q2,q3q0,q1,q2qi,q2终止状态q2,q3q2,q3qOq2,q3终止状态q1,q2,q3q2,q3q0,q1,q2q1,q2,q3q"q32q0,q1,q2.2q3,q1,q22J /nrS|0 02qO0qi吆仁图3-10所示NFA等价的DFAif*12.证明对于任意的NFA,存在与之等价的NFA,该NFA最多只有一个终止状态(刘饪02282083 )证明：对于任 意的
24、NFAM=(Q,刀，3, q0, F),我们如果能构造出一个只有一个终止状 态的NFA,并且与之等价，即可证明上面的 定理而对于任意的NFA存在下面两种情况：(1) 终止状态只有一个(2) 终止状态有多个要构造这个等价的NFA,可以采用如下方法：对无需变化，该NFA即为满足条件的NFA对可以在该NFA的状 态图上添加一个新的终止状态，并将原来的多个终止状态所连接的弧复制到该状态上，此时这个终止状态为新状态图 屮唯一的终止状态，且这个新的NFA与原NFA等价，满足条件 我们总能构造出这样的NFA因此对于任意的NFA,存在与之等价的NFA,该NFA最多只有一个终止状态*林*林*林*林*林*林*林*
25、ofotc*林13 .试给出一个构造方法，对于任意的NFA Mi =(Qi,V, T, qo,Fi),构造NFAM2 =(Q2，2,qo,F2),使得 L(M2)八丄(MJ 证明：(周期律02282067)首先构造一个与NFAMi等价的DFA, M3根据定理3.1 (P106) , L(M3)=L(MJ构造 M3=(Q,> 3,q°,F3),其中Qa =2QI,F3 = PI3P2.Pm |pi, P2.PmQ, Pi , P".Pm Fi =,»,、3(qi.qn,a)ziPiPm=、i (q.qn, a)r. Pi.Pm在此基础上 M2，Q2 =Q3j&
26、#39; 2= 3jF2 = PiPm |Pi Prn F3 二即取所有Mi确定化后不是终结状态的状态为M?的终结状态。为了证明L(M2)二a *丄(M3),我们在M3的基础上M4= (Q4,；4,q°,F4),其中Q4二Q3,、： 4= , F4 = Q4,即所有Mi确定化后的状态都为终结状态。显然L(M4)八XL(M2),则、(q°,x)F“二(q°,x) F3厂二X'L(M3),又因为(q0,x) Q3二'(q°,x) F4二、(q°,x)L(M r,故 x、*-L(M3),故L(M2)丄M)同理容易证明L(M2) = 7
27、<-L(M3)* *故 L(M2)=為丄(M3),又因为 L(M3)=L(MJ,故 L(M2)可知，构造的M2是符合要求的。*«*««*«««*«««*«W仃*仃仃仃*灯仃*i4构造识别下列语言的& -NFAo(吴贤02282047)(1) x x 0,1 +且x中含形如iOiiO的子串 Ux | x 0,i +和x的倒数第i0 个字符是i,且以0i结尾。P2.P m Q,a 1L(Mi)解：得到的NFA如下所示：OJ（2） x x 0,1 +且x中含形如10110的子串x x 0
28、,1 +和x的倒数第10个字符是1,且以 01结尾0. 10,10O0, 10, 11解：得到的&NFA如下所示：0,1x 0,1 +且X以0开头以1结尾。0, 1 0, 1 0,1»O f O O f O-（3） x x0,1 +且x屮不含形如10110的子串Ux 解：关键是构造第一个FA方法是设置5个状态：qo：表示开始状态，以及连续出现了两个以上的0时所进入的状态。Q1表示q。状态下接受到1时（即开始状态或2个以上的0后输入1时）所进入的状 :态。q2表示5状态下接受到0时（即开始状态或2个以上的0后输入10时）所进入 的状 :态。43表示q2状态下接受到1时（即开始状
29、态或2个以上的0后输入101时）所进入 的状 :态。中：表示qs状态下接受到1时（即开始状态或2个以上的0后输入1011时）所进 入的状 态。故得到的e-NFA如下所示：（4）x x 0,1 +且x中不含形如00的子串x | x 0,1 +且x中不含形如11的子串 ° 解:得到的&NFA如下所示:1 _ 005 1 0, 1另外，本题可以构造DFA如下（其屮qt为陷阱状态）：Q2qsx0,1+且x中不含形如11的子11的子串，故x屮只能是01相间的(5) x x0,1 +且x中不含形如00的子串 Ax串 O解：由于x中既不含形如00的子串，又不含形如串。所以，得到的NFA如下
30、所示：Ee另外，本题可以构造DFA如下(其中q+为陷阱状态)1*15.根据NFAM3的状态转移函数，起始状态qo的 闭包为-CLOSURE (q) =qo,q?。由此对以 后每输入一个字符后得到的新状态再做；闭包，得到下表：(陶文婿02282085)状态01q 0,q2qo,qi,q2 q o,qi,q2,q3 q 0,qi,q2 qo,qi,q2,q3 q o,qi,q2,q3 q o, qi, 2, q3 q o,qi2, 3 q o.qn Q2? Q3)qo=qo,q2, qi= q o,qi,q2,q2= q o,qi, q2, q3),因为 q3 为终止状态,所以 q2= q o,q
31、i,q2,q3为终止状态（2）又上述方法得状态01qg q 3,02 q 0, qi,q2,q3 q 312 q3, 2qoq,q3 q 0,qi,q23 q 1, q2,3 q 04x2,43 qo,qi,q3 q 1, q2,3qo.q1.q2, qs q 1,q2,3 q 3® q o?qi23)qo= q i,q3,q.= q 3, q2), q2= q o,qi,q2, q3), q3= q o, qs, q3), q4= q 1, q2, q3因为各状态均含00qiQ3有终止状态，所以q°qq2,q3,q4均为终止状态注：本题没有必要按照NFA到DFA转化的方法
32、来做，而且从NFA到NFA转化时状态没有必要改变, 可以完全采用NFA中的状态如（1）状态01qo （开始状态） q 6 qi q? q'qaqi.q2.q3qi q 0)q1,q2 q3qq2q3Q2 q 0, qi q2 q3q1q2q3qs （终止状态） qo.q i,q2,qaqoqgq状态01qo （开始状态） q qq 3, q o,q i,q2, qsqiq2qgq27273q° q2 q3qa （终止状态）空qo16.证明对于一的 FAMi=(Qi,EiJSi,qoi,Fn, FA Mg 刀 2,3 2,q”2),存在 FAM,使得 L (M) =L (M J
33、U L (M2)(褚颖娜 02282072)证明：不妨设Qi与Q2的交集为空(1)构造 M= (ChUQ2Uq。,刀,S,qo,F)其中:1) 刀=E 1 UE 2 F= F1UF22) S (qo, e )= q 01 ,q°2对于一 q Qi,aE 1 S (q, a)= S i(q,a)对于-q Q2,aE 2, S (q, a)= S2(q,a)(3) 证明: 1)首先证 L(M i)U L(M 2) L(M)设 x L(M i)U L(M 2),从而有 x L(M 1)或者 x L(M 2),当 x e L(M 1)时S 1 (qoi ,x) F1由M的定义可得：S (qo
34、,x) = S (qo, e x) = S ( S (q。，e ), x)= S (q 01 ,q°2,x)= S (qoi, x) U S (qo2, x)=S i(qoi, x) U S (qoi, x) F1 U S (qoi, x)即 x L(M)同理可证当x L(M 2)时x L(M)故 L(M i)UL(M2)L(M)2)再证明 L(M) L(M i)UL(M2)设 x e L(M)则 S ( qo,x ) F由M的定义：S (qo,x) = S (qo, e x) = S ( S (q。，e ), x)= S (q 01 ,q°2,x) = S (qoi, x
35、) U S (qo2, x)如果是S (qoi, x)因为Qi与Q2的交集为空 而且S (qo,x) F F= F1 U F2贝S (qoi, x)= S i(qoi, x) F1 因此 x L(M 1)如果是S (qo2, x)因为Qi与Q2的交集为空 而且S (qo,x) F F= F1 U F2贝S (qo2, x)= S 2(qo2, x) F1 因此 x e L(M 2)因此 x L(M i)U L(M2) L(M) L(M 1) U L(M 2)得证因此 L(M)= L(Mi)UL(M 2)it*(唐明珠 02282084)17 证明：对于任意的 FA Mi = (Qi, 1,诂，
36、q°i, FJ, FAM 2= (Q2,_2 严 2,qz F2),存在 FA M,使得 L(M) =L(Mi)L(M2).证明：令M =(Qi Q2，q°i,f?),其中S的定义为：1)对一 q Qi-f i, aEU e3 (q, a)=3 1 (q , a);2) 对-q Q2-f2, aEU & 3(q, a；=S2(q, a);3) 3 (fi, & )=q 02要证 L(M)二 L(MJL(M2),只需证明 L(MJL(MJ二 L(M), L(MJL(M2匚 L(M) 1 .证明 L(MJL(M2)L(M)设 x L(Mi)L(M2),从而有 x
37、L(MJ并且 x2 L(M2),使得X = XlX2M ,在处理捲的过程中,经过的状态全部都是Oi中的状态，所以在定义M 时，对-q Qa ：-二，、(q,x) = (q,a)故、心 01,咅)二、X2)二fjM 2在处理X2的过程中,经过的状态全部都是Q2中的状态，所以在定义M 时，对一 qQa 二,、(q,x)二 2(q,a)(qo2, x) = r 2(qoi, x) 吩下面证明L(M)、(q%x)二、(q°i,XiX2)=(qoi,Xi),X2)(f rx2)二(fl, X2)二、(> (f r；),x2)-，(q02 * X2J=» 202 ' *2
38、)7即得证xL(M)2)再证明L(M) L(M!)L(M2)设xL(M),即、(qi,x) =f2由于M是从q°i启动的，由M的定义可知,M要达到状态怯必须 先到£由于除了对应状态转移函数式;(fiJ = q02的移动夕卜，不存 在从仏出发的任何其他移动，而且该移动是的必经 移动,所以， 比存在X的前缀Xi和后缀X2,使得咲议2,并且Xi将M从状态qoi引导 到状态fi,x?将M从状态q02引导到状态f2即、(qo,x)二、©1,皿)=s(fi,X2)冷)=6 (q x )这表明xL(M JX4(M2)从而 x = XjX2 L(M OL(M 2)故 L(M) L
39、(Mi)L(M2)综上所述，L(MaL(Mi)L(M2if*(吴丹 02282090)18证明:对于任意的 FAML(QJ'Z； ,®qoi,),FA M2=( Qzg 2,§2002,& ) 存在 FAM,使得 LM= LMa|LM2o证明：不妨将这些FA看成DFA取M 二 Q1 Q29 c, r, qoi, q。？ , F对于-a : 工 H2, q, P 卢 Q,、q,p , a= nq, a ,学 p, a .1 设：x L M 贝I x=x1x2xk 其中 xi i1,ki_ 二 Pr2使得q,p, xi = Tq, xi A 2 P, xi.xi LMi riLMzhX LMjILM?从而可得L M L Mi Dl M22 设：x L Mi IT M2