形式语言与自动机理论蒋宗礼第三章参考复习资料.docx

第三章作业答案1DFA 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)*+(001+11)(01+1+000)*2构造以下语言的DFA ( 陶文婧 02282085 )10，1*20，1+3x|xÎ0，1+且x中不含00的串设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态4 x|xÎ0，1*且x中不含00的串可承受空字符串，所以初始状态也是承受状态5x|xÎ0，1+且x中含形如10110的子串6x|xÎ0，1+且x中不含形如10110的子串设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态7x|xÎ0，1+且当把x看成二进制时，x模5和3同余，要求当x为0时，|x|=1,且x¹0时，x的首字符为1 1. 以0开头的串不被承受，故设置陷阱状态，当DFA在启动状态读入的符号为0，那么进入陷阱状态2. 设置7个状态：开场状态qs,q0:除以5余0的等价类，q1：除以5余1的等价类,q2:除以5余2的等价类，q3:除以5余3的等价类，q4:除以5余4的等价类，承受状态qt3. 状态转移表为状态01q0q1q2q1q3q2q2q0q4q3q1q2q4q3q4 8x|xÎ0，1+且x的第十个字符为1设置一个陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态 9x|xÎ0，1+且x以0开头以1结尾设置陷阱状态，当第一个字符为1时，进入陷阱状态10x|xÎ0，1+且x中至少含有两个111x|xÎ0，1+且如果x以1结尾，那么它的长度为偶数；如果x以0结尾，那么它的长度为奇数可将0，1+的字符串分为4个等价类。q0： e的等价类，对应的状态为终止状态q1:x的长度为奇且以0结尾的等价类q2：x的长度为奇且以1结尾的等价类q3: x的长度为偶且以0结尾的等价类q4: x的长度为偶且以1结尾的等价类12x|x是十进制非负数13F14e3 (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 +并且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,1Set(q0)= Set(q1)=x | 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,q1,q2,q10=0,1当0<=i<=8时候，(q i,0)= ( q i,1)=qi+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(q10)=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 +,并且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 | 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)=十进制正小数13Set(q0)= Set(q0)=14Set(q0)= 4 在例3-6中，状态采用的形式，它比拟清楚地表达出该状态所对应的记忆内容，给我们解决此问题带来了很大的方便，我们是否可以直接用代替呢？如果能，为什么？如果不能，又是为什么？从此问题的讨论，你能总结出什么来？ 唐明珠 02282084答：我认为能够直接用代替，因为在例3-6中，只是一种新的表示方法，用来表示状态存储的字符，这样就省去了在中逐一给出每一个具体的输入字符和状态的定义。它的作用在于使FA中状态定义更加简洁。得到结论：在今后描述FA时，应该根据具体的情况，使用适当的方法。5试区别FA中的陷阱状态和不可达状态。 吴贤珺 02282047解： 陷阱状态课本97页：指在其它状态下发现输入串不可能是该FA所识别的句子时所进入的状态。FA一旦进入该状态，就无法离开，并在此状态下，读完输入串中剩余的字符。 不可达状态课本108页：指从FA的开场状态出发，不可能到达的状态。就FA的状态转移图来说，就是不存在从开场状态对应的顶点出发，到达该状态对应顶点的路径。 从两者的定义可见：相对于不可达状态来说，陷阱状态是可达的。但是，它们都是状态转移图中的非正常状态。如果从状态转移图中的状态引一条弧到不可达状态，同时不可达状态所有的移动都是到自身。这样，不可达状态就变成了陷阱状态。注：此题目有问题，可以将题设改为：x中0和1个数相等且交替出现6证明：题目有不严密之处，图中给出DFA及题目中的语言LM=x|x xÎ0，1+ 且x中0的个数和1的个数相等不完全对应，首先图中的DFA可承受空字符串，而LM不承受，其次，对于有些句子，例如1100，LM可以承受，但DFA不承受1根据图中的DFA可看出，右下角的状态为陷阱状态，所以去除陷阱状态 2由DFA可构造出及其对应的右线性文法： 刘钰 02282083 由此可以看出该文法承受的语言为L=(10|01)*,显然01或10分别是作为整体出现的，所以L(M)中0和1的个数相等。7设DFA M=，证明：对于注：采用归纳证明的思路证明： (周期律 )首先对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)=*LM1。证明：1构造M2。设DFA M1=(Q,q0,F1) 取DFA M2=(Q,q0,QF1) 2证明L(M2)=*LM1对任意xÎ*xÎ L(M2)=*LM1Û(q,x)ÎQF1Ûq,xÎQ并且q,xÏF1ÛxÎ*并且xÏL(M1)ÛxÎ*LM19. 对于任意的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 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 am-1a1L(M1)L(M)=L(M1)T得证 3将-NFA M 确定化 首先构造及-NFA M=( Q, q0, q01) 等价的NFA M3=( Q,2, q0, q01) 其中对于"q,aQ* 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 吴玉涵02282091这是最根本的单元，其他的可以通过这个逐级构造出来，以满足题目要求。*11.根据给定的NFA，构造及之等价的DFA. 吴丹 022820901 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终止状态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等价的DFA2NFA 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,q3图3-10所示NFA等价的DFA12证明对于任意的NFA，存在及之等价的NFA,该NFA最多只有一个终止状态 刘钰 02282083证明：对于任意的NFA M=(Q，q0，F) ，我们如果能构造出一个只有一个终止状态的NFA，并且及之等价，即可证明上面的定理而对于任意的NFA存在下面两种情况：(1)终止状态只有一个(2)终止状态有多个要构造这个等价的NFA,可以采用如下方法：对(1)无需变化，该NFA即为满足条件的NFA对(2)可以在该NFA的状态图上添加一个新的终止状态，并将原来的多个终止状态所连接的弧复制到该状态上，此时这个终止状态为新状态图中唯一的终止状态，且这个新的NFA及原 NFA等价，满足条件我们总能构造出这样的NFA因此对于任意的NFA，存在及之等价的NFA,该NFA最多只有一个终止状态13试给出一个构造方法，对于任意的NFA ，构造NFA ，使得注：转化成相应的DFA进展处理，然后可参考第8题的思路证明： (周期律 )首先构造一个及NFA 等价的DFA ，根据定理3.1P106，构造其中在此根底上，即取所有确定化后不是终结状态的状态为的终结状态。为了证明，我们在的根底上，其中，即所有确定化后的状态都为终结状态。显然那么又因为故，故同理容易证明故，又因为，故可知，构造的是符合要求的。14构造识别以下语言的-NFA。 (吴贤珺 ) 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中含形如10110的子串 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时即开场状态或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中既不含形如00的子串，又不含形如11的子串，故x中只能是01相间的串。所以，得到的-NFA如下所示：0110S 另外，此题可以构造DFA如下其中q+为陷阱状态：S0101010110qt0,1151根据NFAM3的状态转移函数，起始状态q0的e闭包为 e-CLOSUREq0= 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, q1，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，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终止状态空 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,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,xF由M的定义：q0,x=q0,x=(q0,), x)=(q01 ,q02,x) =(q01 , x)(q02, x)如果是(q01 , x) 因为Q1 及Q2的交集为空 而且q0,xF F= F1F2 那么(q01 , x)= 1(q01 , x)F1 因此xL(M1)如果是(q02 , x) 因为Q1 及Q2的交集为空 而且q0,xF 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)唐明珠 0228208417 证明：对于任意的FA 证明：令 ,其中的定义为： 1) 对"qQ1-f1，a (q，a)=1(q，a)； 2)  对"qQ2-f2，a (q，a)=2(q，a)； 3) (f1，)=q02 要证 ，只需证明 ， 1. 证明 2) 再证明吴丹 0228209019、总结本章定义的所有FA，归纳出它们的特点，指出它们之间的差异。吴玉涵02282091本章学习了DFA，NFA，-NFA，2DFA和2NFA所有的FA都是一个五元组M=Q，q0，F最大的区别就是状态转移函数对于DFA，字母表中的每个字母都有唯一确定的状态转移函数。也就是说q，aQ×，qQ，a只有唯一确定的状态。对于NFA，对于字母表中的每个输入字符可以有不同的状态转移，对于串，是一个到自身的移动。对于-NFA，是指在不承受任何字符的情况下，自动机的状态可以发身转移。对于2DFA，对于字母表中的每个字符，对于每个状态都有唯一的状态转移，即q，aQ×，qQ，a只有唯一确定的状态。及DFA不同的是，2DFA的读头可以在一次状态转移中不移动，或者回退一个，或者向下读一个。对于2NFA，及2DFA相似，但是并不是对于字母表中的每个输入字符都有转移函数，2NFA及2DFA的区别类似于DFA及NFA的区别。20构造如图3-20所个的DFA对应的右线性文法。 (周期律 )对图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对应的左线性文法。 (吴贤珺 ) 图形如下所示0010, 1101q0q1q2q3S解：设q0、q1、q2、q3所对应的字符分别为A、B、C、G。由于q2为不可达状态，故先去掉该状态。得到该图所对应的左线性文法为：GA1B11BG0G1A00AB0 图形如下所示：q0q1q2q3S0110100, 101解：图中有多个终结状态，为方便起见，增加一个终结状态红色表示，设该状态所对应的字符为G。又设q0、q1、q2、q3所对应的字符分别为A、B、C、D。那么该图所对应的左线性文法为：GC0B0DC0CB0A11BC1D0D1A00AB122.根据以下给定文法，构造相应的FA。 敖雪峰 02282068(1) 文法G1的产生式集合如下： G1: Sa|AaAa|Aa|cA|BbBa|b|c|aB|Bb|Cb(2) 文法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)=qset(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 q324，总结规约及派生的对应关系，以及及FA的识别过程的对应关系。段季芳 答：对于左线性文法来说，句子a1a2.an-1an按派生来看，字符在句子中出现的顺序是相反的，即anan-1a2a1按规约来看，被规约成语法变量的顺序和他们在句子中出现的顺序 是一致的，即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)文法构造对应的FA 为了形如 所以E=F, 对于产生式 下面证明G(E)及FA等价,即证明L(G(E)=L(M) 不会： 2根据FA ，构造相应的G(E) 为了方便起见，在根据给定的FA构造等价的左线性文法的之前，先对FA做如下的处理：1. 删除FA的陷阱状态。2. 在FA中增加一个识别状态3. “复制一条原来到达终止状态的弧，使它从原来的起点出发，到达新添加的识别状态。 相应的文法的构造依照如下两条进展：1. 如果2. 如果。吴丹 0228209027证明定理3-7 (周期律 )证明：因为FA是一种特殊的2NFA，他是当时，都有，此时的D只为往右移动，即一个每一个状态读入一个字符后读头都往右移动指向下一字符的2NFA，故对任意的FA，定会找到一个及之等价的2NFA及之对应。因此我们只需要证明对任何的2NFA ，都存在FA及之等价。对于任何的2NFA ，构造FA ，按三个方式构造：1如果那么；2如果那么如果，那么；如果，那么重复第二步；如果，那么对于集合A = ，。3如果那么设集合A = ，28证明定理3-8：