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

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

1、第三章作业答案1已知DFA M1与M2如图318所示。 (敖雪峰 02282068)(1) 请分别给出它们在解决字符串1011001的过程中通过的状态序列。(2) 请给出它们的形式描述。 图318 两个不同的DFA解答：(1)M1在解决1011001的过程中通过的状态序列为q0q3q1q3q2q3q1q3; M2在解决1011001的过程中通过的状态序列为q0q2q3q1q3q2q3q1;(2)考虑到用形式语言表达,用自然语言似乎不是那么容易,因此用图上作业法把它们用正则体现式来描述:M1: 01+(00+1)(11+0)11+(10+0)(11+0)*M2: (01+1+000)(01)*+

2、(001+11)(01+1+000)*2构造下列语言的DFA ( 陶文婧 02282085 )（1）0，1*（2）0，1+ （3）x|x0，1+且x中不含00的串（设立一种陷阱状态，一旦发既有00的子串，就进入陷阱状态） （4） x|x0，1*且x中不含00的串（可接受空字符串，因此初始状态也是接受状态）（5）x|x0，1+且x中含形如10110的子串（6）x|x0，1+且x中不含形如10110的子串（设立一种陷阱状态，一旦发既有00的子串，就进入陷阱状态） （7）x|x0，1+且当把x当作二进制时，x模5和3同余，规定当x为0时，|x|=1,且x0时，x的首字符为1 1. 以0开头的串不被接

3、受，故设立陷阱状态，当DFA在启动状态读入的符号为0，则进入陷阱状态2. 设立7个状态：开始状态qs,q0:除以5余0的等价类，q1：除以5余1的等价类,q2:除以5余2的等价类，q3:除以5余3的等价类，q4:除以5余4的等价类，接受状态qt3. 状态转移表为状态01q0q1q2q1q3q2q2q0q4q3q1q2q4q3q4 （8）x|x0，1+且x的第十个字符为1（设立一种陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态） （9）x|x0，1+且x以0开头以1结尾（设立陷阱状态，当第一种字符为1时，进入陷阱状态） （10）x|x0，1+且x中至少具有两个1 （11）x|x0，1+且如果

4、x以1结尾，则它的长度为偶数；如果x以0结尾，则它的长度为奇数可将0，1+的字符串分为4个等价类。q0： e的等价类，相应的状态为终结状态q1:x的长度为奇且以0结尾的等价类q2：x的长度为奇且以1结尾的等价类q3: x的长度为偶且以0结尾的等价类q4: x的长度为偶且以1结尾的等价类（12）x|x是十进制非负数（13）F（14）e*3 (1) （张友坤02282061）=0,1Set(q0)=x | x * (2)=0,1Set(q0)= Set(q1)=x | x + （3）=0,1Set(q0)= Set(q1)=x | x +并且x中不含形如00的子串 Set(q2)=x | x +并

5、且x中不含形如00的子串 (4)=0,1Set(q0)=x | x *并且x中不含形如00的子串 Set(q1)=x | x *并且x中不含形如00的子串 (5)=0,1Set(q0)= x | x *,并且x0*或者x中含形如100的子串 Set(q1)=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(q1)=x |

6、x0+Set(q2)=x | x *,并且x中不含形如10110的子串并且x中具有1Set(q3)=x | x *,并且x中不含形如10110的子串并且x中具有1(7)=0,1Set(qs)= Set(qe)= 0Set(q1)=x | x +,并且把x当作二进制数时，x% 5=1Set(q2)=x | x +,并且把x当作二进制数时，x% 5=2Set(q3)=x | x +,并且把x当作二进制数时，x% 5=3Set(q4)=x | x +,并且把x当作二进制数时，x% 5=4Set(q0)=x | x +,并且把x当作二进制数时，x% 5=0并且x不为0(8)M=Q, ,q0,FQ=q0

7、,q1,q2,q10=0,1当0=i=8时候，(q i,0)= ( q i,1)=q（i+1）( q 9,1)=q10(q 10,0)= ( q 10,1)=q10F= q 10Set(q0)= Set(q1)= 0,1Set(q2)=x | x +,并且|x|=2Set(q3)=x | x +,并且|x|=3Set(q4)=x | x +,并且|x|=4Set(q5)=x | x +,并且|x|=5Set(q6)=x | x +,并且|x|=6Set(q7)=x | x +,并且|x|=7Set(q8)=x | x +,并且|x|=8Set(q9)=x | x +,并且|x|=9Set(q1

8、0)=x | x +,并且x的第十个字符是1(9) M=Q, ,q0,FQ=q0,q1,q2 =0,1(q 0,0)=q1(q 1,0)= q1(q 1,1)= q2(q 2,1)= q2(q 2,0)= q1F= q 2Set(q0)= Set(q1)=x | x +,并且x以0开头以0结尾 Set(q2)=x | x +,并且x以0开头以1结尾 (10) M=Q, ,q0,FQ=q0,q1,q2 =0,1(q 0,0)=q0(q 0,1)=q1(q 1,0)= q1(q 1,1)= q2(q 2,1)= q2(q 2,0)= q2F= q 2Set(q0)= 0*Set(q1)=x | x

9、 +,并且x中只有一种1 Set(q2)=x | x +,并且x至少有俩个1(11) M=Q, ,q0,FQ=q0,q1,q2 , q3,q4 =0,1(q 0,0)=q1(q 0,1)=q4(q 1,0)= q3(q 1,1)= q2(q 2,1)= q4(q 2,0)= q1(q 3,0)= q1(q 3,1)= q4(q 4,1)= q2(q 4,0)= q3F= q 0 ,q 1 ,q 2Set(q0)= Set(q1)=x | x +,以0结尾，长度为奇数 Set(q2)=x | x +,以1结尾，长度为偶数 Set(q3)=x | x +,以0结尾，长度为偶数 Set(q4)=x

10、| x +,以1结尾，长度为奇数 (12)M=Q, ,q0,FQ=q0,q1,q2,q3,q4=.,0,1,2,9F=q1,q2,q4(q 0,0)=q1(q 0,1|2|3|4|5|6|7|8|9)=q2(q 1, . )=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)=q4(q 4,0|1|2|3|4|5|6|7|8|9)=q4Set(q0)= Set(q1)=0 Set(q2)=十进制正整数Set(q3)=十进制非负整数背面接个小数点 . Set(q4)=十进制正小数（13）Set(q0)= Set(

11、q0)=（14）Set(q0)= *4 在例3-6中，状态采用的形式，它比较清晰地体现出该状态所相应的记忆内容，给我们解决此问题带来了很大的以便，我们与否可以直接用替代呢？如果能，为什么？如果不能，又是为什么？从此问题的讨论，你能总结出什么来？ （唐明珠 02282084）答：我觉得可以直接用替代，由于在例3-6中，只是一种新的表达措施，用来表达状态存储的字符，这样就省去了在中逐个给出每一种具体的输入字符和状态的定义。它的作用在于使FA中状态定义更加简洁。得到结论：在此后描述FA时，应当根据具体的状况，使用合适的措施。*5试区别FA中的陷阱状态和不可达状态。 （吴贤珺 02282047）解：

12、陷阱状态（课本97页）：指在其他状态下发现输入串不也许是该FA所辨认的句子时所进入的状态。FA一旦进入该状态，就无法离开，并在此状态下，读完输入串中剩余的字符。 不可达状态（课本108页）：指从FA的开始状态出发，不也许达到的状态。就FA的状态转移图来说，就是不存在从开始状态相应的顶点出发，达到该状态相应顶点的途径。 从两者的定义可见：相对于不可达状态来说，陷阱状态是可达的。但是，它们都是状态转移图中的非正常状态。如果从状态转移图中的状态引一条弧到不可达状态，同步不可达状态所有的移动都是到自身。这样，不可达状态就变成了陷阱状态。*注：此题目有问题，可以将题设改为：x中0和1个数相等且交替浮现6

13、证明：题目有不严密之处，图中给出DFA与题目中的语言L（M）=x|x x0，1+ 且x中0的个数和1的个数相等不完全相应，一方面图中的DFA可接受空字符串，而L（M）不接受，另一方面，对于有些句子，例如1100，L（M）可以接受，但DFA不接受（1）根据图中的DFA可看出，右下角的状态为陷阱状态，因此清除陷阱状态 （2）由DFA可构造出与其相应的右线性文法： （刘钰 02282083） 由此可以看出该文法接受的语言为L=(10|01)*,显然01或10分别是作为整体浮现的，因此L(M)中0和1的个数相等。*7设DFA M=，证明：对于注：采用归纳证明的思路证明： (周期律02282067)一方

14、面对y归纳，对任意x来说，|y| = 0时，即y=根据DFA定义,故原式成立。当|y| = n时，假设原式成立，故当|y|= n+1时，不妨设y = wa, |w| = n, |a| = 1根据DFA定义，故原式成立，同理可证，对任意的y来说，结论也是成立的。综上所述，原式得证*8证明:对于任意的DFA M1=(Q,q0,F1) 存在DFA M2=(Q,q0,F2), （冯蕊 02282075）使得L(M2)=*L（M1）。证明：（1）构造M2。设DFA M1=(Q,q0,F1) 取DFA M2=(Q,q0,QF1) （2）证明L(M2)=*L（M1）对任意x*x L(M2)=*L（M1）(q

15、,x)QF1（q,x）Q并且（q,x）F1x*并且xL(M1)x*L（M1）*9. 对于任意的DFA M1=(Q1,1,q01,F1),请构造DFA M1=(Q2,2,q02,F2)，使得L(M1)=L(M2)T 。其中L(M)T=x|xTL(M) （褚颖娜 02282072）(1) 构造-NFA M 使得 L(M)=L(M1) 取-NFA M=( Q, q0, q01) 其中:1) Q= Q1 q0, q0 Q1 2) 对于 q,pQ1,a,如果1(q,a)=p,q(p,a)3) (q0,)= F1(2) 证明：L(M)=L(M1)T对 x=a1 a2 amL(M)q0 a1 a2 amqf

16、 a1 a2 ama1 q1 a2 ama1 a2 q2 ama1 a2qm-1ama1 a2am q01其中qf(q0,), q1(qf, a1), q2(q1, a2),q01(qm-1, am) 并且qfF1则1(q01, am)= qm-1, 1(qm-1, am-1)= qm-2,1(q2, a2)= q11(q1, a1)= qf因此q01 am am-1a1am qm-1 am-1a1am am-1q2 a2 a1am am-1 a2 q1a1am am-1 a2 a1qf因此am am-1a1L(M1) 即 xTL(M1)同理可证对于 x=a1 a2 amL(M1) xT=am

17、 am-1a1L(M1)L(M)=L(M1)T得证 （3）将-NFA M 拟定化 一方面构造与-NFA M=( Q, q0, q01) 等价的NFA M3=( Q,2, q0, q01) 其中对于（q,a）Q* 2(q,a)= (q,a) 然后按照此前学过的措施构造与NFA M3=( Q,2, q0, q01)等价的DFA M1=(Q1,1,q0,F1) 其中：Q1=2Q F1= q011(q1,q2 , ,qn,a)=p1,p2 ,pn 当且仅当2(q1,q2 , ,qn ,a)= p1,p2 ,pn *注：此题（10题）张友坤、吴玉涵所做完全同样！10、构造辨认下列语言的NFA （吴玉涵0

18、2282091）这是最基本的单元，其她的可以通过这个逐级构造出来，以满足题目规定。*11.根据给定的NFA，构造与之等价的DFA. （吴丹 02282090）（1） NFA M1 的状态转移函数如表3-9状态阐明状态输入字符012开始状态q0q0,q1q0,q2q0,q2q1q3,q0q2q2q3,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终结状

19、态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, q2图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,

20、q1,q2q1,q2,q3q0, q1,q2q0,q1,q2q1,q2q2,q3q0,q1,q2q1, q2终结状态q2,q3q2,q3q0q2,q3终结状态q1,q2,q3q2,q3q0,q1,q2q1, q2,q3图3-10所示NFA等价的DFA*12证明对于任意的NFA，存在与之等价的NFA,该NFA最多只有一种终结状态 （刘钰 02282083）证明：对于任意的NFA M=(Q，q0，F) ，我们如果能构造出一种只有一种终结状态的NFA，并且与之等价，即可证明上面的定理而对于任意的NFA存在下面两种状况：(1)终结状态只有一种(2)终结状态有多种要构造这个等价的NFA,可以采用如下措施

21、：对(1)无需变化，该NFA即为满足条件的NFA对(2)可以在该NFA的状态图上添加一种新的终结状态，并将本来的多种终结状态所连接的弧复制到该状态上，此时这个终结状态为新状态图中唯一的终结状态，且这个新的NFA与原NFA等价，满足条件我们总能构造出这样的NFA因此对于任意的NFA，存在与之等价的NFA,该NFA最多只有一种终结状态*13试给出一种构造措施，对于任意的NFA ，构造NFA ，使得注：转化成相应的DFA进行解决，然后可参照第8题的思路证明： (周期律02282067)一方面构造一种与NFA 等价的DFA ，根据定理3.1（P106），构造其中在此基本上，即取所有拟定化后不是终结状态

22、的状态为的终结状态。为了证明，我们在的基本上，其中，即所有拟定化后的状态都为终结状态。显然则又由于故，故同理容易证明故，又由于，故可知，构造的是符合规定的。*14构造辨认下列语言的-NFA。 (吴贤珺 02282047) xx0,1+ 且x中含形如10110的子串 xx0,1+ 和x的倒数第10个字符是1，且以01结尾 。 解：得到的-NFA如下所示：0, 10, 11110000S00, 110, 10, 10, 10, 10, 10, 10, 1010, 100, 11110000S00, 110, 10, 10, 10, 10, 10, 10, 101 xx0,1+ 且x中含形如1011

23、0的子串 xx0,1+ 和x的倒数第10个字符是1，且以01结尾 解：得到的-NFA如下所示：0, 10, 111100000, 110, 10, 10,1 10, 10, 10,1 110, 101S xx0,1+ 且x中不含形如10110的子串 xx0,1+且x以0开头以1结尾 。解：核心是构造第一种FA，措施是设立5个状态：q0：表达开始状态，以及持续浮现了两个以上的0时所进入的状态。q1: 表达q0状态下接受到1时（即开始状态或2个以上的0后输入1时）所进入的状态。q2: 表达q1状态下接受到0时（即开始状态或2个以上的0后输入10时）所进入的状态。q3: 表达q2状态下接受到1时（即

24、开始状态或2个以上的0后输入101时）所进入的状态。q4: 表达q3状态下接受到1时（即开始状态或2个以上的0后输入1011时）所进入的状态。故得到的-NFA如下所示：S0110q1q0q2q3q410110F00, 11s0s1s21 xx0,1+ 且x中不含形如00的子串 xx0,1+ 且x中不含形如11的子串 。解：得到的-NFA如下所示：10110, 101000, 1S此外，本题可以构造DFA如下（其中qt为陷阱状态）：q0q10q21S111q40q5100q3001q601qt0, 1 xx0,1+ 且x中不含形如00的子串 xx0,1+ 且x中不含形如11的子串 。解：由于x中

25、既不含形如00的子串，又不含形如11的子串，故x中只能是01相间的串。因此，得到的-NFA如下所示：0110S 此外，本题可以构造DFA如下（其中q+为陷阱状态）：S0101010110qt0,1*15（1）根据NFAM3的状态转移函数，起始状态q0的e闭包为 e-CLOSURE（q0）= q0, q2。由此对后来每输入一种字符后得到的新状态再做e闭包，得到下表： （陶文婧 02282085）状态01 q0, q2 q0, q1，q2 q0, q1，q2，q3 q0, q1，q2 q0, q1，q2，q3 q0, q1，q2，q3 q0, q1，q2，q3 q0, q1，q2，q3 q0, q

26、1，q2，q3q0= q0, q2，q1= q0, q1，q2，q2= q0, q1，q2，q3，由于q3为终结状态，因此q2= q0, q1，q2，q3为终结状态（2）又上述措施得状态01 q1, q3 q3，q2 q0, q1，q2，q3 q3，q2 q3，q2 q0, q1，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，q3q0= q1, q3，q1= q3，q2，q2= q0, q1，q2，q3，q3= q0, q1，q3，q4= q1，q2，

27、q3由于各状态均具有终结状态，因此q0, q1，q2，q3,q4均为终结状态注：本题没有必要按照NFA到DFA转化的措施来做，并且从e-NFA到NFA转化时状态没有必要变化，可以完全采用e-NFA中的状态如（1）状态01q0(开始状态) q0, q1，q2 q3 q0, q1，q2，q3q1 q0, q1，q2，q3 q1，q2，q3q2 q0, q1，q2，q3q1，q2，q3q3（终结状态） q0, q1，q2，q3 q0, q1，q2，q3(2) 状态01q0(开始状态) q1 q2 q3， q0, q1，q2，q3q1 q2 q1，q2q2，q2，q3 q0, q2，q3q3（终结状态

28、）空 q0 *16. 证明对于的FA M1=(Q1,1,1,q01,F1)，FA M1=(Q2,2,2,q02,F2)，存在FA M，使得 L(M)= L(M1)L(M2) （褚颖娜 02282072）证明：不妨设Q1 与Q2的交集为空（1） 构造M=（Q1Q2 q0, q0,F）其中：1）=12 F= F1F22) (q0,)= q01 ,q02 对于 qQ1,a1(q, a)=1(q,a) 对于 qQ2,a2 ,(q, a)=2(q,a)(3) 证明：1）一方面证L(M1)L(M2)L(M)设 x L(M1)L(M2)，从而有x L(M1)或者x L(M2)，当x L(M1)时1(q01,

29、x)F1 由M的定义可得：（q0,x）=（q0,x）=(q0,), x)=(q01 ,q02,x)=(q01 , x)(q02, x)=1(q01 , x) (q01 , x)F1(q01 , x) 即xL(M)同理可证当x L(M2)时xL(M)故L(M1)L(M2)L(M) 2) 再证明L(M)L(M1)L(M2)设xL(M) 则（q0,x）F由M的定义：（q0,x）=（q0,x）=(q0,), x)=(q01 ,q02,x) =(q01 , x)(q02, x)如果是(q01 , x) 由于Q1 与Q2的交集为空 并且（q0,x）F F= F1F2 则(q01 , x)= 1(q01 ,

30、 x)F1 因此xL(M1)如果是(q02 , x) 由于Q1 与Q2的交集为空 并且（q0,x）F F= F1F2 则(q02 , x)= 2(q02 , x)F1 因此xL(M2)因此xL(M1)L(M2) L(M)L(M1)L(M2)得证因此L(M)= L(M1)L(M2)*（唐明珠 02282084）17 证明：对于任意的FA . 证明：令 ,其中的定义为： 1) 对qQ1-f1，a (q，a)=1(q，a)； 2) 对qQ2-f2，a (q，a)=2(q，a)； 3) (f1，)=q02 要证 ，只需证明 ， 1. 证明 2) 再证明 *（吴丹 02282090）*19、总结本章定义

31、的所有FA，归纳出它们的特点，指出它们之间的差别。（吴玉涵02282091）本章学习了DFA，NFA，-NFA，2DFA和2NFA所有的FA都是一种五元组M=（Q，q0，F）最大的区别就是状态转移函数对于DFA，字母表中的每个字母均有唯一拟定的状态转移函数。也就是说（q，a）Q，qQ，a只有唯一拟定的状态。对于NFA，对于字母表中的每个输入字符可以有不同的状态转移，对于串，是一种到自身的移动。对于-NFA，是指在不接受任何字符的状况下，自动机的状态可以发身转移。对于2DFA，对于字母表中的每个字符，对于每个状态均有唯一的状态转移，即（q，a）Q，qQ，a只有唯一拟定的状态。与DFA不同的是，2

32、DFA的读头可以在一次状态转移中不移动，或者回退一种，或者向下读一种。对于2NFA，与2DFA相似，但是并不是对于字母表中的每个输入字符均有转移函数，2NFA与2DFA的区别类似于DFA与NFA的区别。*20构造如图3-20所个的DFA相应的右线性文法。 (周期律02282067)对图1：构造文法G=（V，T，P，S），其中V=S，A，B，C，T=1，0P：对图2：构造文法G=（V，T，P，S），其中V=S，A，B，C，T=1，0P：*21构造下图所示DFA相应的左线性文法。 (吴贤珺 02282047) 图形如下所示0010, 1101q0q1q2q3S解：设q0、q1、q2、q3所相应的字

33、符分别为A、B、C、G。由于q2为不可达状态，故先去掉该状态。得到该图所相应的左线性文法为：GA1B11BG0G1A00AB0 图形如下所示：q0q1q2q3S0110100, 101解：图中有多种终结状态，为以便起见，增长一种终结状态（红色表达），设该状态所相应的字符为G。又设q0、q1、q2、q3所相应的字符分别为A、B、C、D。则该图所相应的左线性文法为：GC0B0DC0CB0A11BC1D0D1A00AB1*22.根据下列给定文法，构造相应的FA。 （敖雪峰 02282068）(1) 文法G1的产生式集合如下： G1: Sa|AaAa|Aa|cA|BbBa|b|c|aB|Bb|Cb(2

34、) 文法G2的产生式集合如下： G2: Sa|Aa Aa|Aa|Ac|Bb Ba|b|c|Ba|Bb|Bc解答: 文法G1相应的FA如下所示文法G2相应的FA如下所示*23.FA M的移动函数定义如下: （冯蕊 02282075）(q0,3)=q0(q0,1)=q1(q1,0)=q2(q1,1)=q3(q2,0)=q2(q3,1)=q3其中,q2,q3为终态.(1) M是DFA吗?为什么?不是,由于并不是所有的状态,在接受一种字母表中的字符时会有一种状态与之相应.(2) 画出相应的DFA的状态转移图(3) 给出你所画出的DFA的每个状态q的set(q):set(q)=x|x*且(q0,x)=q

35、set(q0)=3* set(q1)= 3*1 set(q2)= 3*100* set(q3)= 3*111*set(q)=( 3*0|3*13|3*100*(1|3)|3*111*(0|3) 0*1*3*(4) 求正则措施G,使L(G)=L(M)q03 q0|1 q1q10 q2|1 q3q20|0 q2q31|1 q3*24，总结规约与派生的相应关系，以及与FA的辨认过程的相应关系。（段季芳02282073）答：对于左线性文法来说，句子a1a2.an-1an按派生来看，字符在句子中浮现的顺序是相反的，即anan-1a2a1按规约来看，被规约成语法变量的顺序和她们在句子中浮现的顺序 是一致的

36、，即a1a2.an-1anFA辨认时，如果存在状态转移（A，a）=B，表达A后紧跟一种a时，要规约到B；如果B是终结符号，则A后紧跟一种a时，要规约到该文法的开始符号；如果A是开始状态，则a要规约到B。对于右线性文法来说，句子a1a2.an-1an按派生来看，字符在句子中浮现的顺序也就是a1a2.an-1an按规约来看，被规约成语法变量的顺序和她们在句子中浮现的顺序 是相反的，即anan-1a2a1FA辨认时，如果存在状态转移（A，a）=B，则表达遇到A则派生成aB；但如果B是终结符号，则将A推导为a。*25 证明左线性文法与FA等价。 （唐明珠 02282084）证明：1）根据左线性G(E)

37、文法构造相应的FA 为了形如 因此E=F, 对于产生式 下面证明G(E)与FA等价,即证明L(G(E)=L(M) 不会：） 2）根据FA ，构造相应的G(E) 为了以便起见，在根据给定的FA构造等价的左线性文法的之前，先对FA做如下的解决：1. 删除FA的陷阱状态。2. 在FA中增长一种辨认状态3. “复制”一条本来达到终结状态的弧，使它从本来的起点出发，达到新添加的辨认状态。 相应的文法的构造根据如下两条进行：1. 如果2. 如果。*（吴丹 02282090）*27证明定理3-7 (周期律02282067)证明：由于FA是一种特殊的2NFA，她是当时，均有，此时的D只为往右移动，即一种每一种

38、状态读入一种字符后读头都往右移动指向下一字符的2NFA，故对任意的FA，定会找到一种与之等价的2NFA与之相应。因此我们只需要证明对任何的2NFA ，都存在FA与之等价。对于任何的2NFA ，构造FA ，按三个方式构造：1如果则；2如果则如果，则；如果，则反复第二步；如果，则对于集合A = ，。3如果则设集合A = ，*28证明定理3-8：Moore机与Mealy机等价 （郭会 0228）证明：不妨设Moore机，Mealy机，则根据Moore机和Mealy机等价的定义知，必须证明：,其中T1(x)和T2(x)分别表达M1和M2有关x的输出。（1） 构造M2， （2） 证明，不妨设则M1的输出为:由题意可知均为Moore机中的状态，由（1）中的构造假设知，M2的输出为：（1） 构造M1， （2） 证明，不妨设则M1的输出为:由题意可知均为Mealy机中的状态，由（1）中的构造假设知，M1的输出为：综上所述，Moore机与Mealy机等价