形式语言与自动机理论

《形式语言与自动机理论》由会员分享，可在线阅读，更多相关《形式语言与自动机理论（33页珍藏版）》请在装配图网上搜索。

1、第三章作业答案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)

2、(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的子

3、串（设置一个陷阱状态，一旦发现有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

4、 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-力力力力力力力 $&个个个个个

5、个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个(张友坤 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=

6、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中不含形如1011

7、0的子串而且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

8、(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的

9、第十个字符是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

10、 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结

11、尾，长度为偶数 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

12、(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 呢？如果能，为什么？如果不能，又是为什么？从此问题的讨论，你能

13、总 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一旦进入该状态，就无法离开，并在此状态下，读完输

14、入串中 剩余的字符。不可达状态(课本108页)：指从FA的开始状态出发，不可能到达的状态。就FA 的状态转移图来说，就是不存在从开始状态对应的顶点出发，到达该状态对应顶点 的路径。从两者的定义可见：相对于不可达状态来说，陷阱状态是可达的。但是，它们都是 状态转移图中的非正常状态。如果从状态转移图中的状态引一条弧到不可达状态， 同时不可达状态所有的移动都是到自身。这样，不可达状态就变成了陷阱状态。力 $ 力、*注：此题目有问题，可以将题设改为：X中0和1个数相等且交替出现6. 证明：题目有不严密之处，图中给出DFA与题目中的语言L (M) =x|xx0，1+且x 中0的个数和1的个数相等不完全对

15、应，首先图中的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 ,

16、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 ，

17、故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(M

18、2)=*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,pQi,ae

19、E,如果 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(qi，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 % %

20、 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= q

21、0i5 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

22、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状态说明状态输入字符01

23、2开始状态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,

24、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,

25、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最多只有一个终止状态(刘钰 022820

26、83)证明：对于任意的NFA M=(Q,E,S, q0, F)，我们如果能构造出一个只有一个终止状 态的NFA,并且与之等价，即可证明上面的定理而对于任意的NFA存在下面两种情况：(1) 终止状态只有一个(2) 终止状态有多个要构造这个等价的NFA,可以采用如下方法：对(1)无需变化，该NFA即为满足条件的NFA对(2)可以在该NFA的状态图上添加一个新的终止状态，并将原来的多个终止状态所连接的 弧复制到该状态上，此时这个终止状态为新状态图中唯一的终止状态，且这个新的NFA与 原NFA等价，满足条件我们总能构造出这样的NFA因此对于任意的NFA，存在与之等价的NFA,该NFA最多只有一个终止状

27、态&$*!-力力力力力 $“$ 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

28、= (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

29、 ,F )，其 23344404中Q4=Q3,54= F4=Q4，即所有M1确定化后的状态都为终结状态。显然L(M4) = *,n5(q0,x)Pl F3 wn 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

30、。(吴贤珺 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时）所进入 的状态

31、。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的子串，又不含形如

32、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

33、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 q

34、2 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&

35、$*!-力力力力力 $“$ 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 ,q0

36、2对于V qGQ1,aeE1 8 (q, a)= 5 i(q,a)对于V qQ2,aE2, 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(

37、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 因此 xL(M1)如果是6(q02 , x)因为Q1与Q2的交集为空而且6(q0,x)GF F= F1UF2贝6 (q02 , x)= 6 2

38、(q02 , x)GF1 因此 xL(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存在 FA M,使得 L(M) = L(M1)L(M2).证明：令 M = (Q1Q2,Z,8 ,q01,f2),其中6的定义为：1)对VqEQj-ifJ, aEU e 8 (q, a)= 8 1(q, a)；2) 对VqEQ2-f2，aEU 8

39、(q, a)=82(q, a)；3) 8(f1，)=q02要证 L(M ) = L(M )L( )，只需证明 L(M )L(M ) c L(M) , L(M )L(M ) m L(M)1.证明 L(M1)L(M2) c L(M)设x e L(M )L(M ),从而有工 e L(M )并且x e L(M ), 121122使得x = x xm 在处理气的过程中,经过的状态全部都是q中的状态，所以在定义M时，对Vg e Q , a e E, 5 (q, x) = 5 (q, a)故8(q ,x ) =5 (q ,x ) = f 01110121M 2在处理七的过程中,经过的状态全部都是中的状态，所

40、以在定义M时，对Vq e Q , a e E, 8 (q, x) = 5 (q, a)5(q ,x) =5 (q ,x) = f 022012下面证明 x e L(M)5 (q , x) = 5 (q , x x )01011 2=5 (5 (q , x ), x )= 5 (5 (q , x ), x ) 10112=5 (f, x 2)=5 (f, x2)=5 (5 (f, 8), x 2)= 5 (q02 , x2 )=5 (q ,x )2022=f2即得证x e L(M)2)再证明L(M) c L(M )L(M )设x e L(M)，艮口5 (q 01, x) = f由于M是从q：启动

41、的，由M的定义可知,心要达到状态八，必须 先至虬.由于除了对应状态转移函数式5 (f1，8) = q02 的移动 外，不存在从1出发的任何其他移动，而且该移动是2的必经 移动,所以,比存在x的前缀x和后缀x，使得x = x x ,并且x121 21将心从状态q引导到状态/ ,x将心从状态q引导到状态/ 0112022即5 (q , x) = 5 (q ,x x )01011 2=5 (f1，x 2)=5 (f1，8x 2)=5 (q , x )这表明x g L(M )x g L(M ) 从而x = xx g L(M )L(M ) 1 212故L(M) q L(M ) L(M )综上所述，12L

42、( M) = L( M1) L (M 2* (吴丹 02282090)FA M =(Q Z 8 q F )22, 2, 2, 02, 218.证明：对于任意的FAM=(Q. Z 8 q.F) 存在FAM，使得L(M)=L(M )AL(M )。12证明：不妨将这些FA看成DFA212 /01、02(q,p)g Q?(q,p, a)= 8 (q, a), 8 (p, a).取M =(Q x Q/Zf Z2, 8,q0, q， 对于Va gZJIZ2，一 / _ 1(1) 设：x g L(M)则女=x1 x2xk其中xz4 g Q,k) 使得8(Iq,p, xi)=81(q, xi),8 (p, x

43、i) /. xi g L(M. )nL(M )n x g L(M. )p|L(M ) 从而可得 L (M )q L (Mn L (mJ(2) 设：x g L(M )nL(M )则女=x1 x2.xk其中xiG gI1,k)g Z AZ 有8 (q, xi)且82 (p, xi)从而使得 81 (q,xi )=8(Iq,p,xi)； 8 (p, xi)=8(q,p, xi)xi g L(m)n x g L(m) 从而可得L(MjnL(M )q L(M) 综合(1)(2)可得L(M)=L(MnL(mJ。 又因为faBdfa具有等价性，所以原命题得证。“ 个个个个个个个个个个个个个个个个个个个个个个

44、个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个19、总结本章定义的所有FA,归纳出它们的特点，指出它们之间的差别。（吴玉涵02282091）本章学习了 DFA，NFA,e -NFA, 2DFA和 2NFA所有的FA都是一个五元组M=（Q,N，5, q0, F）最大的区别就是状态转移函数5对于DFA，字母表中的每个字母都有唯一确定的状态转移函数。也就是说V 5（q, a）EQ XS, qGQ，aEN只有唯一确定的状态。对于NFA，对于字母表中的每个输入字符可以有不同的状态转移，对于8串，是一个到自 身的移动。对于sNFA，是指在不接

45、受任何字符的情况下，自动机的状态可以发身转移。对于2DFA，对于字母表中的每个字符，对于每个状态都有唯一的状态转移，即V 5 （q，a） EQXS，qEQ，aES只有唯一确定的状态。与DFA不同的是，2DFA的读头可以在一次 状态转移中不移动，或者回退一个，或者向下读一个。对于2NFA，与2DFA相似，但是并不是对于字母表中的每个输入字符都有转移函数，2NFA 与2DFA的区别类似于DFA与NFA的区别。“ *20构造如图3-20所个的DFA对应的右线性文法。（周期律02282067）对图1：构造文法G= （V，T，P，S），其中V=S，A，B，C，T=1，0S T 0 A |1| 1CA t

46、 0S |1|1CP：B t 01 0C |1SC T 0 A |1A对图2：构造文法G= （V，T，P，S），其中V=S，A，B，C，T=1，0S T 0 A |1BA t1S |1|0BP：B t 0C |0|1AC T 0 A |1A“ *21.构造下图所示DFA对应的左线性文法。（吴贤珺02282047）图形如下所示解：设q0、q1、q2、q3所对应的字符分别为A、B、C、G。由于q2为不可达状态，故先去掉该状态。得到该图所对应的左线性文法为:G-A1 |B1|1B-G0 |G1|A0|0AB0图形如下所示:解：图中有多个终结状态，为方便起见，增加一个终结状态（红色表示），设该状 态所

47、对应的字符为G。又设q0、q1、q2、q3所对应的字符分别为A、B、C、D。 则该图所对应的左线性文法为：G-C0 |B0|eD-C0C-B0 |A1|1B-C1 |D0|D1|A0|0A-B1*22.根据下列给定文法，构造相应的FA。(敖雪峰02282068)(1)文法G1的产生式集合如下：G1: S-alAaA-alAalcAlBbBalblclaBIBblCb(2)文法G2的产生式集合如下：G2: SalAaAalAalAcIBbBalblcIBalBblBc解答：文法G1对应的FA如下所示e“$ 力力力力力力力力 $ 力、mi，&“$ 力力力“*23.FA M的移动函数定义如下：(冯蕊

48、02282075)5 %3)叫6 (q0，1)=(q15 (q1,0)=q26 (q1?1)=q35 (q2,0)=q25 (q3,1)=q3其中,q2,q3为终态.(1) M是DFA吗?为什么？不是，因为并不是所有的状态,在接收一个字母表中的字符时会有一个状态与之对应.(2) 画出相应的DFA的状态转移图0,1,3 给出你所画出的DFA的每个状态q的set(q):set(q)=xlx N *且5 (q0,x)=q set(q0)=3*set(q1)= 3*1set(q2)= 3*100*set(q3)= 3*111*set(q)=( 3*013*1313*100*(113)13*111*(0

49、13) 0*1*3* 求正则方法G/吏L（G）=L（M）q03 q0|1 q1qL0 q2|1 q3q2 一010 q2q3m q3*24,总结规约与派生的对应关系，以及与FA的识别过程的对应关系。（段季芳02282073）答：对于左线性文法来说，句子a1a2. .an-1an按派生来看，字符在句子中出现的顺序是相反的，即anan-1.a2a1按规约来看，被规约成语法变量的顺序和他们在句子中出现的顺序是一致的，即.气-1*FA识别时，如果存在状态转移5（A，a） =B，表示A后紧跟一个a时，要规约到B；如果 B是终结符号，则A后紧跟一个a时，要规约到该文法的开始符号；如果A是开始状态， 则a要规约到B。对于右线性文法来说，句子a1a2. .an-1an按派生来看，字符在句子中出现的顺序也就是a1a2.an-1an按规约来看，被规约成语法变量的顺序和他们在句子中出现的顺序是相反的，即anan-1.a2a1FA识别时，如果存在状态转移5（A，a） =B，则表示遇到A则派生成aB；但如果B是终 结符号，则将A推导为a。*25证明左线性文法与FA等价。（唐明珠02282084）证明：1）根据左线性G（E）文法构造对应的FA M = （Q, Z,6 , q0, F）为了形如A 。的产生式，增加一个开始状态Z，使得q0= Z