形式语言与自动机理论.docx

第三章作业答案1.已知DFA M1与M2如图3 18所示。(敖雪峰 02282068)(1) 请分别给出它们在处理字符串1011001的过程中经过的状态序列。(2) 请给出它们的形式描述。S0图3 18两个不同的DFA解答：(1)M 1在处理1011001的过程中经过的状态序列为q0q3q1q3q2q3q1q3;M2在处理1011001的过程中经过的状态序列为q0q2q3q 1 q3q2q3q 1;(2)考虑到用形式语言表示，用自然语言似乎不是那么容易，所以用图上作业法把它们用正则 表达式来描述：M1: 01+(00+1)(11+0)11+(10+0)(11+0)*M2: (01+1+000)(01)*+(001+11)(01+1+000)*个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个2.构造下列语言的DFA(1)(陶文婧 02282085 )(2)0, 1*0, 10， 1+(3) xlx 0, 1+且x中不含00的串(设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态)S（4） xlxe0, 1*且x中不含00的串（可接受空字符串，所以初始状态也是接受状态）S1（5）xlxe0，1+且x中含形如10110的子串0（6）xlxe0，1+且x中不含形如10110的子串（设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态）（7）xlxe0， 1+且当把x看成二进制时，x模5和3同余，要求当x为0时，凤=1,且x0 时，x的首字符为1 1.以0开头的串不被接受，故设置陷阱状态，当DFA在启动状态读入的符号为0，则进 入陷阱状态2.设置7个状态：开始状态qs,q0.除以5余0的等价类，除以5余1的等价类,q2.除以5 余2的等价类，q3.除以5余3的等价类，q4.除以5余4的等价类，接受状态qt（8） （xlxe0, 1+且x的第十个字符为1（设置一个陷阱状态，一旦发现x的第十个字符为0,进入陷阱状态）厂、厂、厂、s 厂、cST山马叫马 04 马v v U AJ（9）xlxe0， 1+且x以0开头以1结尾（设置陷阱状态，当第一个字符为1时，进入陷阱状态）S（10）xlxe0，1+且x中至少含有两个1则它的长度（11） xlxe0, 1+且如果x以1结尾，则它的长度为偶数；如果x以0结尾， 为奇数可将0，1+的字符串分为4个等价类。q0国的等价类，对应的状态为终止状态q1：x的长度为奇且以0结尾的等价类q2 x的长度为奇且以1结尾的等价类q3： x的长度为偶且以0结尾的等价类q4： x的长度为偶且以1结尾的等价类S（12）xlx是十进制非负数5，6，7，8，9（13）中S（14）£S&$*!-力力力力力 $“$ kJ-力力力力力力力 $&个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个(张友坤 02282061)310Z=o,iSet(q0)=x I xG Z*(2)Z=o,iSet(q0)=eSet(ql)=x I xG Z + (3)Z=o,iSet(q0)= eSet(ql)=x I xe Z +并且x中不含形如00的子串Set(q2)=x I xe Z +并且x中不含形如00的子串 Z=0,lSet(q0)=x I xe Z *并且x中不含形如00的子串Set(ql)=x I xe Z *并且x中不含形如00的子串nZ=O,1Set(q0)= (xSet(ql)=x 11 xexeZ*,并且x60*或者x中含形如100的子串 Z *,并且X中含形如1的子串Set(q2)=x 1xeZ*,并且x中含形如10的子串Set(q3)=x 1xeZ*,并且x中含形如101的子串Set(q4)=x 1xeZ*,并且x中含形如1011的子串Set(q5)=(x 1xeZ*,并且x中含形如10110的子串(6)Z=O,1Set(qO)= S )Set(ql)=(x I xg 0+Set(q2)=x I xe Z *,并且x中不含形如10110的子串而且x中含有1 Set(q3)=x I xe Z *,并且x中不含形如10110的子串而且x中含有1 (7)0Z=o,iSet(qs)= 8 Set(qe)= 0Set(ql)=(x I x Z+,并且把x看成二进制数时，x% 5=1)Set(q2)=x I xe Z+,并且把x看成二进制数时，x% 5=2Set(q3)=x I x e E +,并且把x看成二进制数时，x% 5=3Set(q4)=x I xe Z +,并且把x看成二进制数时，x% 5=4Set(q0)=x I xe E +,并且把x看成二进制数时，x% 5=0并且x不为0(8)M=Q, E , § ,q0,F。=%月1月2，E =0,1当0<=i<=8时候，§ (q0)= § ( qiFi+D§( q9,1)=q10§ (q 1o，0)= §( q10,1)=q10F= q 10Set(q0)= 8 Set(q1)= 0,1Set(q2)=x | x e E +,并且 1x1=2Set(q3)=x | x e E +,并且 1x1=3Set(q4)=x | x e E +,并且 1x1=4Set(q5)=x | x e E +,并且 |x|=5Set(q6)=x | x e E +,并且 |x|=6Set(q7)=x | x e E +,并且 |x|=7Set(q8)=x | x e E +,并且 |x|=8Set(q9)=x | x e E +,并且 |x|=9Set(q10)=x | xe E +,并且x的第十个字符是1 M=Q, E ,§ ,q0,FQ=q0,q1,q2 E =0,1§ (q 0,0)=q1§ (q 1,0)= q1§ (q 1,1)= q2§ (q 2，1)= q2§ (q 2，0)= q1F= q?Set(q0)= 8 Set(q1)=x | xe E +,并且x以0开头以0结尾Set(q2)=x | x e E +,并且x以0开头以1结尾(10) M=Q, E ,§,q0,FQ=q0,q1,q2 E =0,1§ (q 0,0)=q0§ (q 0,1)=q1§ (q 1,0)= q18 (q i)=q28 (q拱片q28 (q 2,0)= q2F= q2)Set(q0)= 0*Set(q1)=x I xe E +,并且 x 中只有一个 1 Set(q2)=x I xe Z +,并且x至少有俩个1(11) M=Q, 1,8 ,q0,FQ=q0,q1,q2 , q3,q4 E =0,18 (q 0,0)=q18 (q 0,1)=q48 (q 1,0)= q38 (q 1,1)= q28 (q 2,1)= q48 (q 2,0)= q18 (q 3,0)= q18 (q 3,1)= q48 (q 4,1)= q28 (q 4,0)= q3F= q0 ,q1 ,q2Set(q0)= 8 Set(q1)=x | xe E +,以0结尾，长度为奇数 Set(q2)=x | x e E +,以1结尾，长度为偶数 Set(q3)=x | x e E +,以0结尾，长度为偶数 Set(q4)=x | xe E +,以1结尾，长度为奇数(12)M=Q, E ,8 ,q0,FQ=q0,q1,q2,q3,q4E = .,0,1,2,.,9F=q1,q2,q48 (q 0,0)=q18 (q 0,1|2|3|4|5|6|7|8|9)=q28 (q 1, . )=q28 (q 2,0|1|2|3|4|5|6|7|8|9)=q28 (q 2, . )=q38 (q 3,0|1|2|3|4|5|6|7|8|9)=q48 (q 4,0|1|2|3|4|5|6|7|8|9)=q4Set(q0)= 8 Set(q1)=0 Set(q2)=十进制正整数Set(q3)=十进制非负整数后面接个小数点. Set(q4)=十进制正小数(13)Set(q0)= 8 Set(q0)= 0(14)Set(q0)= 8 个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个4在例3-6中，状态采用qa a .a 的形式，它比较清楚地表达出该状态所对应的记忆内1 2 n容，给我们解决此问题带来了很大的方便，我们是否可以直接用%a2.。代替qa a .a 呢？如果能，为什么？如果不能，又是为什么？从此问题的讨论，你能总 1 2 n结出什么来？(唐明珠02282084)答：我认为能够直接用a a .a 代替qa a .a ，因为在例3-6中，qa a .a 只是一1 2 n1 2 n1 2 n种新的表示方法，用来表示状态存储的字符，这样就省去了在8中逐一给出每一个具体 的输入字符和状态的定义。它的作用在于使FA中状态定义更加简洁。得到结论：在今后描述FA时，应该根据具体的情况，使用适当的方法。*5. 试区别FA中的陷阱状态和不可达状态。(吴贤珺02282047)解：陷阱状态(课本97页)：指在其它状态下发现输入串不可能是该FA所识别的句子 时所进入的状态。FA一旦进入该状态，就无法离开，并在此状态下，读完输入串中 剩余的字符。不可达状态(课本108页)：指从FA的开始状态出发，不可能到达的状态。就FA 的状态转移图来说，就是不存在从开始状态对应的顶点出发，到达该状态对应顶点 的路径。从两者的定义可见：相对于不可达状态来说，陷阱状态是可达的。但是，它们都是 状态转移图中的非正常状态。如果从状态转移图中的状态引一条弧到不可达状态， 同时不可达状态所有的移动都是到自身。这样，不可达状态就变成了陷阱状态。力 $ 力、*注：此题目有问题，可以将题设改为：X中0和1个数相等且交替出现6. 证明：题目有不严密之处，图中给出DFA与题目中的语言L (M) =x|xx0，1+且x 中0的个数和1的个数相等不完全对应，首先图中的DFA可接受空字符串，而L (M) 不接受，其次，对于有些句子，例如1100，L (M)可以接受，但DFA不接受(1) 根据图中的DFA可看出，右下角的状态为陷阱状态，所以去除陷阱状态(2) 由DFA可构造出与其对应的右线性文法：(刘钰02282083)S T 0 AA T 1S 11S T 1BB T 0S 10将1S,1代入5 T 0A；0S,0代入5 T 1B得S T 01S 101S T 10 S 110由此可以看出该文法接受的语言为L=(10I01)*,显然01或10分别是作为整体出现的， 所以L(M)中0和1的个数相等。“ *7. 设 DFA M=(0 E, 5 , q 0, F)，证明：对于 Vx, y e *, q e Q, 5 (q, xy) =8 (6 (q, x), y)注：采用归纳证明的思路证明：(周期律02282067)首先对y归纳，对任意x来说，IyI = 0时，即y= e根据 DFA 定义6 (q,S) = q, 6 (q, xy) = 6 (q, x) = 6 (6 (q, x),8) = 6 (6 (q, x), y)做原式成立。当IyI = n时，假设原式成立，故当IyI= n+1时，不妨设 y = wa, IwI = n, IaI = 1根据 DFA 定义6 (q , xa ) = 6 (6 (q , x), a ), a e £，故6 (q, xy) = 6 (q, xwa) = 6 (6 (q, xw), a) = 6 (6 (6 (q, x), w), a) = 6 (6 (q, x), wa) = 6 (6 (q, x), y)原式成立，同理可证，对任意的y来说，结论也是成立的。综上所述，原式得证“ *8. 证明:对于任意的 DFA M1=(Q, £, & ,q0,F1)存在 DFA M2=(Q, £, & ,q0,F2),(冯蕊 02282075)使得 L(M2)=£*L (MJ。证明：(1)构造m2。设 DFA M1=(Q, £, 5 ,q0,F1)取 DFA M2=(Q, £, 5 ,q0,QF1)(2)证明 L(M2)=£*L (M1)对任意xe £ *xe L(M2)=£*L (M1)0 5 (q,x)eQF0 5(q,x) eQ 并且 5(q,x) wF0xe£*并且 xwL(MQxe£*L (M1)“ *9. 对于任意的 DFA M_(Q, E , 5 1,q01,F1),请构造 DFA M1=(Q2, E , 5 2,q02,F2)，使得L(M)=L(M2)t。其中 L(M)t=xIxtEL(M)(褚颖娜 02282072)(1)构造 8-NFA M 使得 L(M)=L(M1)取 8-NFA M=( Q,E, 5 , q0, q01)其中：1) Q= Q1U q0, q0w Q12)对于V q,p£Qi,aeE,如果 5 1(q,a)=p,qE5 (p,a) 3) 5 (qo, £)= Fi(2) 证明：L(M)=L(M1)T对 V x=a1 a2. amEL(M)q° ai %. am E ai a2.am E S 支am E % 42- am IE %-&卜 ai % q01其中 qfE5 (q0, 顷 qi5 (qf, aj q25 (qi, a2),.qoie5 (qm-i, am) 并且 qfGFI则 5 i(q°i，am)= qm-i，5 i(qm-i，am-i)= 4皿-2， 5 iW，%)= S 5 i% 诺=4f因此 qoi am am-i-ai Iam qm-i 弟K %日2 % % K %. % "iIam am-i. % aiqf因此 am am-i.aiEL(Mi)即 xtGL(Mi)同理可证对于 V x=ai a2. am E L(Mi) xT=am ami.ai L(Mi)L(M)=L(M)t 得证(3) 将£ -NFA M确定化首先构造与 £-NFA M=( Q，E，5, qo，( q0i)等价的 NFA M3=( Q，E，5 2，q0，( q0i)其中对于V (q,a)EQ*工 5 2(q,a)= 5 人(q,a)然后按照以前学过的方法构造与NFA M3=( Q,E,52, q0, q0i)等价的DFAMi=(Qi,E,5i,q0,Fi)其中：Q=2q Fi= q0i5 i(qi,q2,. ,qn,a)=pi,p2,.,pn当且仅当 52(qi,q2,. ,qn ,a)= pi,p2,.,pn *注：此题(10题)张友坤、吴玉涵所做完全一样！i0、构造识别下列语言的NFA(吴玉涵0228209i)(i)x|x e 0,i+且尤中不含形如00的子串ii(2)x x e 0,1+且尤中含形如10110的子串0, 1x x e 0,1+且尤中不含形如10110的子串(4) x x e 0,1+和尤的倒数第10个字符是1,且以01结尾0, 1J10，10，10，1o o o o0，1100101010”'(5) x x e 0,1+且尤以0开头以1结尾(6)x x e 0,1+且尤中至少含有两个10，10，10，1(7) xx e 0,1*且如果尤以1结尾，则它的长度为偶数;如果以0结尾，则它的长度为奇数（8）x x e 0,1+且尤的首字符和尾字符相等(9)仙xt x, e 0,1+0,10,1这是最基本的单元，其他的可以通过这个逐级构造出来，以满足题目要求。个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个11.根据给定的NFA，构造与之等价的DFA,（吴丹02282090）（1）NFA M 的状态转移函数如表3-9状态说明状态输入字符012开始状态q0q0,q1q0,q2q0,q2q1q3,q00q2q20q3,q1q2,q1终止状态q3q3,q2q3 q0解答:状态说明状态输入字符012开始状态q0q0,q1q0,q2q0,q2q0,q1q0,q1,q3q0,q2q0,q2q0,q2q0,q1q0,q1,q2,q3q0,q1,q2q0,q1,q2q0,q1,q3q0,q1,q2,q3q0,q1,q2终止状态q0,q1,q3q0,q1,q2,q3q0, 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, q2q00:12 0,41,220,1q0,q21,q22100,1 q0,q1,q2,q32妙的1 0 q0,q1,q3 q0,q2,q3图3-9所示NFA等价的DFA(2) NFA M2的状态转移函数如表3-10状态说明-状态输入字符012开始状态q0q1,q3q1q0 q1q2q1,q2q1q2q3,q2q0q2 终止状态q3q0 q3解答:状态说明状态输入字符012开始状态q0q1,q3q1q0q1,q3q2q0,q1,q2q1,q3q1q2q1,q2q1q2q2,q3q0q2q0,q1,q2q1,q2,q3q0, q1,q2q0,q1,q2q1,q2q2,q3q0,q1,q2q1, q2终止状态q2,q3q2,q3q0q2,q3终止状态q1,q2,q3q2,q3q0,q1,q2q1, q2,q3q0,q1,q2q1,q32 12100q22 0 q2,q3011q1'、.1J 0 02q3,q1,q220图3-10所示NFA等价的DFAe 力力力 $ 力、mi，+ + + + + + + + + + + + +个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个12.证明对于任意的NFA,存在与之等价的NFA,该NFA最多只有一个终止状态(刘钰 02282083)证明：对于任意的NFA M=(Q,E,S, q0, F)，我们如果能构造出一个只有一个终止状 态的NFA,并且与之等价，即可证明上面的定理而对于任意的NFA存在下面两种情况：(1) 终止状态只有一个(2) 终止状态有多个要构造这个等价的NFA,可以采用如下方法：对(1)无需变化，该NFA即为满足条件的NFA对(2)可以在该NFA的状态图上添加一个新的终止状态，并将原来的多个终止状态所连接的 弧复制到该状态上，此时这个终止状态为新状态图中唯一的终止状态，且这个新的NFA与 原NFA等价，满足条件我们总能构造出这样的NFA因此对于任意的NFA，存在与之等价的NFA,该NFA最多只有一个终止状态&$*!-力力力力力 $“$ kJ-力力力力力力力 $&个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个13 .试给出一个构造方法，对于任意的NFA M = (Q ,Z,5 ,q ,F )，构造NFA11101M = (Q , Z, 5 , q , F )，使得 L(M ) = Z * - L(M )2220221注：转化成相应的DFA进行处理，然后可参考第8题的思路证明:(周期律 02282067)首先构造一个与NFA吃等价的DFA ,吃根据定理3.1(P106),顷"(吃)构造M = (Q , Z,5 ,q , F ),其中33303Q = 2Q1，F = p , p .p I p , p .p c Q,p , p .p n F 林,p , p .p c Q,a ”3312 m 12 m12 m 112 m5 (q .q , a) = p .p 。5 (q .q , a) = p .p 31 n1 m11 n1 m在此基础上M，Q = Q ,5 =5 , F = p .p I p .p n F M 2232321 m 1 m 3即取所有M1确定化后不是终结状态的状态为M2的终结状态。为了证明L(M ) 二 £ * - L(M )，我们在M的基础上M = (Q ,Z,5 ,q ,F )，其 23344404中Q4=Q3,54=" F4=Q4，即所有M1确定化后的状态都为终结状态。显然L(M4) = £ *,n5(q0,x)Pl F3 w©n x 冬 L(M3),又 因5(q ,x) e Q n 5(q ,x) e F n 5 (q ,x) e L(M ) = £ *,故 x e£ * -L(M )，Vx e L(M2),则5 (q 0, XF2 州-L( M 3) 同理容易证明L(M2)目£-L( M 3)故L(M2) = £ * - L(M3)又因为L(M3) = L(M1)，故L(M2) = £ * - L(MJ可知，构造的M 2是符合要求的。“ *14.构造识别下列语言的8-NFA。(吴贤珺 02282047) x|xE0,1+且x中含形如10110的子串U x|xE0,1+和x的倒数第10 个字符是1，且以01结尾。解：得到的e -NFA如下所示：eSx|xE0,1+且x中含形如10110的子串x|xE0,1+和x的倒数第10个字符是1,且以01结尾解：得到的e-NFA如下所示：S0,1O x|xE 0,1+且x中不含形如10110的子串U x|xE0,1+且x以0开头以1 结尾。解：关键是构造第一个FA，方法是设置5个状态：q0：表示开始状态，以及连续出现了两个以上的0时所进入的状态。q1：表示q0状态下接受到1时（即开始状态或2个以上的0后输入1时）所进入 的状态。q2：表示状态下接受到0时（即开始状态或2个以上的0后输入10时）所进入 的状态。q3：表示q2状态下接受到1时（即开始状态或2个以上的0后输入101时）所进入 的状态。q4：表示q3状态下接受到1时（即开始状态或2个以上的0后输入1011时）所进 入的状态。故得到的e-NFA如下所示： x|xE0,1+且x中不含形如00的子串 x|xE0,1+且x中不含形如11的 子串。解：得到的e -NFA如下所示：另外，本题可以构造DFA如下（其中qt为陷阱状态）: x| xE 0,1+且x中不含形如00的子串C x|xE0,1+且x中不含形如11的子 串。解：由于x中既不含形如00的子串，又不含形如11的子串，故x中只能是01相间的串。所以，得到的8-NFA如下所示:另外，本题可以构造DFA如下(其中q+为陷阱状态):个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个15. (1)根据NFAM3的状态转移函数，起始状态q0的£闭包为-CLOSURE (q0)= q0 q2。 由此对以后每输入一个字符后得到的新状态再做£闭包，得到下表： (陶文婧02282085)状态01 q0 q2 q0 q】q2 q0 q1 q2 q3 q0 q1 q2 q0 q1 q2 q3 q0 q】q2 q3 q0 q, q2 q3 q0 q q2 q3 q0 q】q2 q3q0= q0q2，q1= q0 q1q2，q2=q0q1 q2 q3，因为q3为终止状态，所以q2=q0q1q2q3为终止状态 Sq(0&（2）又上述方法得状态01 q】q3 q3 q2 q0 q, q2 q3 q3 q2 q3 q2 q0 q q3 q0 q1 q2 q3 q1 q2 q3 q0 q1 q2 q3 q0 q1 q3 q1 q2 q3 q0 q1 q2 q3 q1 q2 q3 q3 q2 q0 q1 q2 q3q°= q1 q3，q q3 q2，q2= q0 i q2 q3，q3= q0 i q3，q4= qi q2 q3 因为各状态均含 有终止状态，所以q0, q1，q2，q3,q4均为终止状态S注：本题没有必要按照NFA到DFA转化的方法来做，而且从s-NFA到NFA转化时状态没有必 要改变，可以完全采用s-NFA中的状态如状态0iq0（开始状态） qo q. % qJ气 &, %, q3q. qo q. % qJ q. q。qJq2 qo q.% qq. q2 qJq3 （终止状态） qo, &,气,qJ qo, qi,q。, qJ状态o1qo（开始状态） q. q2 q3 qo qi q。q_qq" q. q-q2 q。qJ1，2 qo q2 qJq3 （终止状态）, L ,3空O,2,3_id&$*!-力力力力力 $“$ kJ-力力力力力力力 $&个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个16. 证明对于V的 FA M1=(Q1,E1,81,q01,F1)，FA M1=(Q2,E2, 8 2,q02,F2)，存在 FA M，使得 L(M)= L(M1) U L(M2)(褚颖娜 02282072)证明：不妨设Q1与Q2的交集为空(1) 构造 M= (Q1UQ2U q°,；8, q0，F)其中：1) e=e1ue2 f= f1uf22) 6 (q0, e )= q0i ,q02对于V qGQ1,aeE1 8 (q, a)= 5 i(q,a)对于V q£Q2,a£E2, 6 (q, a)= 6 2(q,a)(3)证明：1)首先证 L(M1)UL(M2)EL(M)设 x GL(M1)UL(M2)，从而有 x EL(M)或者 x EL(M2),当 x GL(M1)时61(qo1,x)GF1由M的定义可得：6(q0,x) = 6(qo, e x) =6(6 (qo, e ), x)= 6 (q01 ,q02,x)= 6 (q01 , x)U6 (q02, x)=6 1(q01 , x) U6 (q01 , x)EF U6 (q01 , x)即 xEL(M)同理可证当x EL(M2)时xEL(M)故 L(M)UL(M2)EL(M)2)再证明 L(M)EL(M)UL(M2)设 xEL(M)则 6(q0,x)EF由M的定义：6(q0，x)= 6(q0, e x) = 6 ( 6 (q0, e ), x)= 6 (q01 ,q02，x) = 6 (q01 , x)U6 (q02, x)如果是6(q01 , x)因为Q1与Q2的交集为空而且6(q0,x)GF F= F1UF2贝6 (q01 , x)= 6 1(q01 , x)GF1 因此 x£L(M1)如果是6(q02 , x)因为Q1与Q2的交集为空而且6(q0,x)GF F= F1UF2贝6 (q02 , x)= 6 2(q02 , x)GF1 因此 x£L(M2)因此 x E L(M1) U L(M2)L(M) E L(M1) U L(M2)得证因此 L(M)= L(M1) U L(M2)“ *(唐明珠 02282084)17 证明：对于任意的 FAM = (Q ,£ ,8 ,q , F ), FAM = (Q ,£ ,8 ,q , F ), 11110112222022存