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

形式语言与自动机理论-蒋宗礼-第三章参考答案第三章作业答案1．已知DFAM1与M2如图3－18所示。(敖雪峰02282068)(1)请分别给出它们在处理字符串1011001的过程中经过的状态序列。(2)请给出它们的形式描述。qSq01图3－18两个不同的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)（1）{0，1}*，1（2）{0，1}+，1（3）{x|x?{0，1}+且x中不含00的串}（设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态）（4）{x|x?{0，1}*且x中不含00的串}（可接受空字符串，所以初始状态也是接受状态）（5）{x|x?{0，1}+且x中含形如10110的子串}+（6）{x|x?{0，1}且x中不含形如10110的子串}（设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态）（7）{x|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的等价类，接受状态qt（8）{x|x?{0，1}且x的第十个字符为1}（设置一个陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态）+（9）{x|x?{0，1}+且x以0开头以1结尾}（设置陷阱状态，当第一个字符为1时，进入陷阱状态）（10）{x|x?{0，1}+且x中至少含有两个1}（11）{x|x?{0，1}+且如果x以1结尾，则它的长度为偶数；如果x以0结尾，则它的长度为奇数}可将{0，1}+的字符串分为4个等价类。q0：[?]的等价类，对应的状态为终止状态q1:x的长度为奇且以0结尾的等价类q2：x的长度为奇且以1结尾的等价类q3:x的长度为偶且以0结尾的等价类q4:x的长度为偶且以1结尾的等价类（12）{x|x是十进制非负数}4，95，6，7，8，9（13）?（14）?*******************************************************************************3(1)（张友坤02282061）?={0,1}Set(q0)={x|x??*}(2)?={0,1}Set(q0)=?Set(q1)={x|x??+}（3）?={0,1}Set(q0)=?Set(q1)={x|x??+并且x中不含形如00的子串}Set(q2)={x|x??+并且x中不含形如00的子串}(4)?={0,1}Set(q0)={x|x??*并且x中不含形如00的子串}Set(q1)={x|x??*并且x中不含形如00的子串}(5)?={0,1}Set(q0)={x|x??*,并且x?{0}*或者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|x?{0+}}Set(q2)={x|x??*,并且x中不含形如10110的子串而且x中含有1}Set(q3)={x|x??*,并且x中不含形如10110的子串而且x中含有1}(7)?={0,1}Set(qs)={?}Set(qe)={0}Set(q1)={x|x??+,并且把x看成二进制数时，x%5=1}Set(q2)={x|x??+,并且把x看成二进制数时，x%5=2}Set(q3)={x|x??+,并且把x看成二进制数时，x%5=3}Set(q4)={x|x??+,并且把x看成二进制数时，x%5=4}Set(q0)={x|x??+,并且把x看成二进制数时，x%5=0并且x不为0}(8)M={Q,?,?,q0,F}Q={q0,q1,q2,…q10}?={0,1}当0<=i<=8时候，?(qi,0)=?(qi,1)=q（i+1）?(q9,1)=q10?(q10,0)=?(q10,1)=q10F={q10}Set(q0)={?}Set(q1)={0,1}Set(q2)={x|x??+,并且|x|=2}Set(q3)={x|x??+,并且|x|=3}Set(q4)={x|x??+,并且|x|=4}Set(q5)={x|x??+,并且|x|=5}Set(q6)={x|x??+,并且|x|=6}Set(q7)={x|x??+,并且|x|=7}Set(q8)={x|x??+,并且|x|=8}Set(q9)={x|x??+,并且|x|=9}Set(q10)={x|x??+,并且x的第十个字符是1}(9)M={Q,?,?,q0,F}Q={q0,q1,q2}?={0,1}(q0,0)=q1(q1,0)=q1(q1,1)=q2(q2,1)=q2(q2,0)=q1F={q2}Set(q0)={?}Set(q1)={x|x??+,并且x以0开头以0结尾}Set(q2)={x|x??+,并且x以0开头以1结尾}(10)M={Q,?,?,q0,F}Q={q0,q1,q2}?={0,1}??????(q0,0)=q0?(q0,1)=q1?(q1,0)=q1?(q1,1)=q2?(q2,1)=q2?(q2,0)=q2F={q2}Set(q0)={0}*Set(q1)={x|x??+,并且x中只有一个1}Set(q2)={x|x??+,并且x至少有俩个1}(11)M={Q,?,?,q0,F}Q={q0,q1,q2,q3,q4}?={0,1}(q0,0)=q1(q0,1)=q4(q1,0)=q3(q1,1)=q2(q2,1)=q4(q2,0)=q1(q3,0)=q1(q3,1)=q4(q4,1)=q2(q4,0)=q3F={q0,q1,q2}Set(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,F}Q={q0,q1,q2,q3,q4}?={.,0,1,2,…,9}F={q1,q2,q4}?(q0,0)=q1?(q0,1|2|3|4|5|6|7|8|9)=q2?(q1,.)=q2?(q2,0|1|2|3|4|5|6|7|8|9)=q2?(q2,.)=q3?(q3,0|1|2|3|4|5|6|7|8|9)=q4?(q4,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(q0)=?（14）Set(q0)={?}*******************************************************************************4在例3-6中，状态采用q[a1a2...an]的形式，它比较清楚地表达出该状态所对应的记忆内容，给我们解决此问题带来了很大的方便，我们是否可以直接用[a1a2...an]代替q[a1a2...an]呢？如果能，为什么？如果不能，又是为什么？从此问题的讨论，你能总结出什么来？（唐明珠02282084）答：我认为能够直接用[a1a2...an]代替q[a1a2...an]，因为在例3-6中，q[a1a2...an]只是一种新的表示方法，用来表示状态存储的字符，这样就省去了在?中逐一给出每一个具体的输入字符和状态的定义。它的作用在于使FA中状态定义更加简洁。得到结论：在今后描述FA时，应该根据具体的情况，使用适当的方法。*******************************************************************************5．试区别FA中的陷阱状态和不可达状态。（吴贤珺02282047）解：⑴陷阱状态（课本97页）：指在其它状态下发现输入串不可能是该FA所识别的句子时所进入的状态。FA一旦进入该状态，就无法离开，并在此状态下，读完输入串中剩余的字符。⑵不可达状态（课本108页）：指从FA的开始状态出发，不可能到达的状态。就FA的状态转移图来说，就是不存在从开始状态对应的顶点出发，到达该状态对应顶点的路径。⑶从两者的定义可见：相对于不可达状态来说，陷阱状态是可达的。但是，它们都是状态转移图中的非正常状态。如果从状态转移图中的状态引一条弧到不可达状态，同时不可达状态所有的移动都是到自身。这样，不可达状态就变成了陷阱状态。******************************************************************************注：此题目有问题，可以将题设改为：x中0和1个数相等且交替出现6．证明：题目有不严密之处，图中给出DFA与题目中的语言L（M）={x|xx?{0，1}+且x中0的个数和1的个数相等}不完全对应，首先图中的DFA可接受空字符串，而L（M）不接受，其次，对于有些句子，例如1100，L（M）可以接受，但DFA不接受（1）根据图中的DFA可看出，右下角的状态为陷阱状态，所以去除陷阱状态（2）由DFA可构造出与其对应的右线性文法：（刘钰02282083）S?0AA?1S|1S?1BB?0S|0将1S,1代入S?0A；0S,代入0S?B1得S?01S|01S?10S|10*由此可以看出该文法接受的语言为L={(10|01)},显然01或10分别是作为整体出现的，所以L(M)中0和1的个数相等。******************************************************************************7．设DFAM=(Q,?,?,q0,F)，证明：对于?x,y??*,q?Q,?(q,xy)??(?(q,x),y)注：采用归纳证明的思路证明：(周期律02282067)首先对y归纳，对任意x来说，|y|=0时，即y=?根据DFA定义?(q,?)?q,?(q,xy)??(q,x)??(?(q,x),?)??(?(q,x),y),故原式成立。当|y|=n时，假设原式成立，故当|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)??(?(q,x),y)原式成立，同理可证，对任意的y来说，结论也是成立的。综上所述，原式得证*******************************************************************************8．证明:对于任意的DFAM1=(Q,Σ,δ,q0,F1)存在DFAM2=(Q,Σ,δ,q0,F2),（冯蕊02282075）使得L(M2)=Σ*—L（M1）。证明：（1）构造M2。设DFAM1=(Q,Σ,δ,q0,F1)取DFAM2=(Q,Σ,δ,q0,Q—F1)（2）证明L(M2)=Σ*—L（M1）对任意x?Σ*x?L(M2)=Σ*—L（M1）?δ(q,x)?Q—F1?δ（q,x）?Q并且δ（q,x）?F1?x?Σ*并且x?L(M1)?x?Σ*—L（M1）*******************************************************************************9.对于任意的DFAM1=(Q1,∑,δ1,q01,F1),请构造DFAM1=(Q2,∑,δ2,q02,F2)，使得L(M1)=L(M2)T。其中L(M)T={x|xT∈L(M)}（褚颖娜02282072）(1)构造ε-NFAM使得L(M)=L(M1)取ε-NFAM=(Q,∑,δ,q0,{q01})其中:1)Q=Q1∪{q0},q0?Q12)对于?q,p∈Q1,a∈∑,如果δ1(q,a)=p,q∈δ(p,a)3)δ(q0,ε)=F1(2)证明：L(M)=L(M1)T对?x=a1a2…am∈L(M)q0a1a2…am├qfa1a2…am├a1q1a2…am├a1a2q2…am├…├a1a2…qm-1am├a1a2…amq01其中qf∈δ(q0,ε),q1∈δ(qf,a1),q2∈δ(q1,a2),…q01∈δ(qm-1,am)并且qf∈F1则δ1(q01,am)=qm-1,δ1(qm-1,am-1)=qm-2,…δ1(q2,a2)=q1δ1(q1,a1)=qf因此q01amam-1…a1├amqm-1am-1…a1├amam-1…q2a2a1├amam-1…a2q1a1├amam-1…a2a1qf因此amam-1…a1∈L(M1)即xT∈L(M1)同理可证对于?x=a1a2…am∈L(M1)xT=amam-1…a1∈L(M1)L(M)=L(M1)T得证（3）将ε-NFAM确定化首先构造与ε-NFAM=(Q,∑,δ,q0,{q01})等价的NFAM3=(Q,∑,δ2,q0,{q01})其中对于?（q,a）∈Q*∑δ2(q,a)=δ^(q,a)然后按照以前学过的方法构造与NFAM3=(Q,∑,δ2,q0,{q01})等价的DFAM1=(Q1,∑,δ1,[q0],F1)其中：Q1=2QF1={q01}δ1([q1,q2,…,qn],a)=[p1,p2,…,pn]当且仅当δ2({q1,q2,…,qn},a)={p1,p2,…,pn}*******************************************************************************注：此题（10题）张友坤、吴玉涵所做完全一样！！10、构造识别下列语言的NFA（吴玉涵02282091）(1){xx?{0,1}?且x中不含形如00的子串}(2){xx?{0,1}且x中含形如10110的子串}?(3){xx?{0,1}?且x中不含形如10110的子串}(4){xx?{0,1}?和x的倒数第10个字符是1，且以01结尾}1(5){xx?{0,1}?且x以0开头以1结尾}(6){xx?{0,1}?且x中至少含有两个1}0，1(7){xx?{0,1}*且如果x以1结尾，则它的长度为偶数；如果以0结尾，则它的长度为奇数}(8){xx?{0,1}?且x的首字符和尾字符相等}(9){x?xTx,??{0,1}?}这是最基本的单元，其他的可以通过这个逐级构造出来，以满足题目要求。*******************************************************************************11.根据给定的NFA，构造与之等价的DFA.（吴丹02282090）解答：图3-9所示NFA等价的DFA（2）NFAM的状态转移函数如表3-10****************************************************************************12．证明对于任意的NFA，存在与之等价的NFA,该NFA最多只有一个终止状态（刘钰02282083）证明：对于任意的NFAM=(Q，∑，δ，q0，F)，我们如果能构造出一个只有一个终止状态的NFA，并且与之等价，即可证明上面的定理而对于任意的NFA存在下面两种情况：(1)终止状态只有一个(2)终止状态有多个要构造这个等价的NFA,可以采用如下方法：对(1)无需变化，该NFA即为满足条件的NFA对(2)可以在该NFA的状态图上添加一个新的终止状态，并将原来的多个终止状态所连接的弧复制到该状态上，此时这个终止状态为新状态图中唯一的终止状态，且这个新的NFA与原NFA等价，满足条件我们总能构造出这样的NFA因此对于任意的NFA，存在与之等价的NFA,该NFA最多只有一个终止状态*******************************************************************************13．试给出一个构造方法，对于任意的NFAM1?(Q1,?,?1,q0,F1)，构造NFAM2?(Q2,?,?2,q0,F2)，使得L(M2)??*?L(M1)注：转化成相应的DFA进行处理，然后可参考第8题的思路证明：(周期律02282067)首先构造一个与NFAM1等价的DFA，M3根据定理3.1（P106），L(M3)?L(M1)构造M3?(Q3,?,?3,[q0],F3),其中Q3?2Q1,F3?{[p1,p2...pm]|{p1,p2...pm}?Q,{p1,p2...pm}?F1??},{p1,p2...pm}?Q,a???3([q1...qn],a)?[p1...pm]??1({q1...qn},a)?{p1...pm}在此基础上M2，Q2?Q3,?2??3,F2?{[p1...pm]|[p1...pm]?F3??}即取所有M1确定化后不是终结状态的状态为M2的终结状态。为了证明L(M2)??*?L(M3)，我们在M3的基础上M4?(Q4,?,?4,q0,F4)，其中Q4?Q3,?4??3,F4?Q4，即所有M1确定化后的状态都为终结状态。显然L(M4)??*,?x?L(M2),则?(q0,x)?F2????(q0,x)?F3???x?L(M3),又因为?(q0,x)?Q3??(q0,x)?F4??(q0,x)?L(M4)??*,故x??*?L(M3)，故L(M2)???*?L(M3)同理容易证明L(M2)?故L(M2)?*?*?L(M3)?L(M3)，又因为L(M3)?L(M1)，故L(M2)??*?L(M1)可知，构造的M2是符合要求的。*******************************************************************************14．构造识别下列语言的ε-NFA。(吴贤珺02282047)++⑴{x│x∈{0,1}且x中含形如10110的子串}∪{x│x∈{0,1}和x的倒数第10个字符是1，且以01结尾}。解：得到的ε-NFA如下所示：⑵{x│x∈{0,1}且x中含形如10110的子串}{x│x∈{0,1}和x的倒数第10个字符是1，且以01结尾}解：得到的ε-NFA如下所示：++⑶{x│x∈{0,1}且x中不含形如10110的子串}∪{x│x∈{0,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如下所示：++⑷{x│x∈{0,1}且x中不含形如00的子串}{x│x∈{0,1}且x中不含形如11的子串}。解：得到的ε-NFA如下所示：另外，本题可以构造DFA如下（其中qt为陷阱状态）：⑸{x│x∈{0,1}且x中不含形如00的子串}∩{x│x∈{0,1}且x中不含形如11的子串}。解：由于x中既不含形如00的子串，又不含形如11的子串，故x中只能是01相间的串。所以，得到的ε-NFA如下所示：++另外，本题可以构造DFA如下（其中q+为陷阱状态）：*******************************************************************************15．（1）根据NFAM3的状态转移函数，起始状态q0的?闭包为?-CLOSURE（q0）={q0,q2}。q0={q0,q2}，q1={q0,q1，q2}，q2={q0,q1，q2，q3}，因为q3为终止状态，所以q2={q0,q1，q2，q3}为终止状态2（2）又上述方法得0=1,31=3，22=0,1，2，33=0,1，34=1，2，3有终止状态，所以q0,q1，q2，q3,q4均为终止状态注：本题没有必要按照NFA到DFA转化的方法来做，而且从?-NFA到NFA转化时状态没有必要改变，可以完全采用?-NFA中的状态如（1）*******************************************************************************16.证明对于?的FAM1=(Q1,∑1,δ1,q01,F1)，FAM1=(Q2,∑2,δ2,q02,F2)，存在FAM，使得L(M)=L(M1)∪L(M2)（褚颖娜02282072）证明：不妨设Q1与Q2的交集为空（1）构造M=（Q1∪Q2∪{q0},∑,δ,q0,F）其中：1）∑=∑1∪∑2F=F1∪F22)δ(q0,ε)={q01,q02}对于?q∈Q1,a∈∑1δ(q,a)=δ1(q,a)对于?q∈Q2,a∈∑2,δ(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)即x∈L(M)同理可证当x∈L(M2)时x∈L(M)故L(M1)∪L(M2)∈L(M)2)再证明L(M)∈L(M1)∪L(M2)设x∈L(M)则δ（q0,x）∈F由M的定义：δ（q0,x）=δ（q0,εx）=δ(δ(q0,ε),x)=δ({q01,q02},x)=δ(q01,x)∪δ(q02,x)如果是δ(q01,x)因为Q1与Q2的交集为空而且δ（q0,x）∈FF=F1∪F2则δ(q01,x)=δ1(q01,x)∈F1因此x∈L(M1)如果是δ(q02,x)因为Q1与Q2的交集为空而且δ（q0,x）∈FF=F1∪F2则δ(q02,x)=δ2(q02,x)∈F1因此x∈L(M2)因此x∈L(M1)∪L(M2)L(M)∈L(M1)∪L(M2)得证因此L(M)=L(M1)∪L(M2)*******************************************************************************（唐明珠02282084）17证明：对于任意的FAM1?(Q1,?1,?1,q01,F1),FAM2?(Q2,?2,?2,q02,F2),存在FAM,使得L(M)?L(M1)L(M2).证明：令?(Q1?Q2,?,?,q01,,其中δ的定义为：M{f2})1)对?q∈Q1-{f1}，a∈∑∪{ε}δ(q，a)=δ1(q，a)；2)对?q∈Q2-{f2}，a∈∑∪{ε}δ(q，a)=δ2(q，a)；3)δ(f1，ε)={q02}要证L()?L(M1)L(M2)，M只需证明L(M1)L(M2)?L(M)，(M1)L(M2)L(M)L?1.证明L(ML2L(M)(M)?1)设x?L(M1)L(M2),从而有x1?L(M1)并且x2?L(M2),x?x1x2使得M1在处理x1的过程中,经过的状态全部都是Q1中的状态,所以在定义M时,对?q?Q1,a??,?(q,x)??1(q,a)故?(q01,x1)??1(q01,x2)?{f1}M2在处理x2的过程中,经过的状态全部都是Q2中的状态,所以在定义M时,对?q?Q1,a??,?(q,x)??2(q,a)?(q02,x)??2(q01,x)?{f2}下面证明x?L(M)?(q01,x)??(q01,x1x2)??(?(q01,x1),x2)??(?1(q01,x1),x2)??(f1,x2)??(f1,?x2)??(?(f1,?),x2)??(q02,x2)??2(q02,x2)?{f2}即得证x?L(M)2)再证明L(M)?L(M1)L(M2)设x?L(M),即?(q01,x)?{f2}由于M是从q01启动的,由M的定义可知,M要达到状态f2,必须先到f1.由于除了对应状态转移函数式?(f1,?)?{q02}的移动外,不存在从f1出发的任何其他移动,而且该移动是f2的必经移动,所以,比存在x的前缀x1和后缀x2,使得x?x1x2,并且x1将M从状态q01引导到状态f1,x2将M从状态q02引导到状态f2.即?(q01,x)??(q01,x1x2)??(f1,x2)??(f1,?x2)??(q,x)这表明x1?L(M1)x2?L(M2)从而x?x1x2?L(M1)L(M2)故L(M)?L(M1)L(M2)L(M)?L(M1)L(M2*******************************************************************************（吴丹02282090）综上所述,18.证明：对于任意的FAM1＝?Q1，?1，?1，q01，F1?，FAM2＝?Q2，?2，?2，q02，F2?存在FAM，使得L?M?＝L?M1??L?M2?。证明：不妨将这些FA看成DFA取M＝?Q1?Q2，?1??2，?，?q01，q02?，F?对于?a??1??2，?q,p??Q,???q,p?，a?＝???1?q，a?，?2?p，a???.?1?设：x?L?M?则?x?x1x2......xk其中xi?i??1,k????1??2使得???q,p?，xi?????1?q，xi?,?2?p，xi????xi?L?M1??L?M2??x?L?M1??L?M2?从而可得L?M??L?M1??L?M2??2?设：x?L?M1??L?M2?则?x?x1x2......xk其中xi?i??1,k????1??2有?1?q，xi?且?2?p，xi?从而使得?1?q，xi?＝???q,p?，xi?；?2?p，xi?＝???q,p?，xi??xi?L?M??x?L?M?从而可得L?M1??L?M2??L?M?综合(1)(2)可得L?M?＝L?M1??L?M2?。又因为FA和DFA具有等价性，所以原命题得证。*****************************************************************************19、总结本章定义的所有FA，归纳出它们的特点，指出它们之间的差别。（吴玉涵02282091）本章学习了DFA，NFA，ε-NFA，2DFA和2NFA所有的FA都是一个五元组M=（Q，Σ，δ，q0，F）最大的区别就是状态转移函数δ对于DFA，字母表中的每个字母都有唯一确定的状态转移函数。也就是说?δ（q，a）∈Q×Σ，q∈Q，a∈Σ只有唯一确定的状态。对于NFA，对于字母表中的每个输入字符可以有不同的状态转移，对于ε串，是一个到自身的移动。对于ε-NFA，是指在不接受任何字符的情况下，自动机的状态可以发身转移。对于2DFA，对于字母表中的每个字符，对于每个状态都有唯一的状态转移，即?δ（q，a）∈Q×Σ，q∈Q，a∈Σ只有唯一确定的状态。与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，0}S?0A|1|1CP：A?0S|1|1CB?0|0C|1SC?0A|1A对图2：构造文法G=（V，T，P，S），其中V={S，A，B，C}，T={1，0}S?0A|1BP：A?1S|1|0BB?0C|0|1AC?0A|1A*******************************************************************************21．构造下图所示DFA对应的左线性文法。(吴贤珺02282047)⑴图形如下所示解：设q0、q1、q2、q3所对应的字符分别为A、B、C、G。由于q2为不可达状态，故先去掉该状态。得到该图所对应的左线性文法为：G→A1│B1│1B→G0│G1│A0│0A→B0⑵图形如下所示：解：图中有多个终结状态，为方便起见，增加一个终结状态（红色表示），设该状态所对应的字符为G。又设q0、q1、q2、q3所对应的字符分别为A、B、C、D。则该图所对应的左线性文法为：G→C0│B0│εD→C0C→B0│A1│1B→C1│D0│D1│A0│0A→B1*******************************************************************************22.根据下列给定文法，构造相应的FA。（敖雪峰02282068）(1)文法G1的产生式集合如下：G1:S→a|AaA→a|Aa|cA|BbB→a|b|c|aB|Bb|Cb(2)文法G2的产生式集合如下：G2:S→a|AaA→a|Aa|Ac|BbB→a|b|c|Ba|Bb|Bc解答:文法G1对应的FA如下所示a,ca,b,cAB文法G2对应的FA******************************************************************************23.FAM的移动函数定义如下:（冯蕊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}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)q0→3q0|1q1q1→0q2|1q3q2→0|0q2q3→1|1q3*******************************************************************************24，总结规约与派生的对应关系，以及与FA的识别过程的对应关系。（段季芳02282073）答：对于左线性文法来说，句子a1a2….an-1an按派生来看，字符在句子中出现的顺序是相反的，即anan-1…a2a1按规约来看，被规约成语法变量的顺序和他们在句子中出现的顺序是一致的，即a1a2….an-1anFA识别时，如果存在状态转移δ（A，a）=B，表示A后紧跟一个a时，要规约到B；如果B是终结符号，则A后紧跟一个a时，要规约到该文法的开始符号；如果A是开始状态，则a要规约到B。对于右线性文法来说，句子a1a2….an-1an按派生来看，字符在句子中出现的顺序也就是a1a2….an-1an按规约来看，被规约成语法变量的顺序和他们在句子中出现的顺序是相反的，即anan-1…a2a1FA识别时，如果存在状态转移δ（A，a）=B，则表示遇到A则派生成aB；但如果B是终结符号，则将A推导为a。******************************************************************************25证明左线性文法与FA等价。（唐明珠02282084）证明：1）根据左线性G(E)文法构造对应的FAM?(Q,?,?,q0,F)为了形如A?a的产生式，增加一个开始状态Z，使得q0?Z所以E=F,对于产生式B?Aa,则有?(A,a)?B,对于产生式?B?a,且E是开始状态，则有?(E,a)?B.下面证明G(E)与FA等价,即证明L(G(E))=L(M)不会：）2）根据FAM?(Q,?,?,q0,F)，构造相应的G(E)为了方便起见，在根据给定的FA构造等价的左线性文法的之前，先对FA做如下的处理：1.删除FA的陷阱状态。2.在FA中增加一个识别状态3.“复制”一条原来到达终止状态的弧，使它从原来的起点出发，到达新添加的识别状态。相应的文法的构造依照如下两条进行：1.如果?(A,a)?B，则有产生式B?a2.如果?(A,a)?B,且A是开始状态q0,则有产生式B?a。*******************************************************************************（吴丹02282090）26.证明定理3-6。（2DFA与FA等价）证明：对于2DFAM是一个五元组M＝?Q，?，?，q0，F?其中，Q，?，q0，F的意义同与DFA。?：Q???Q??L，R，S?，对于??q，a??Q??，?1?如果??q，a?＝?p，L?表示在读入a从状态q转移到状态p，并将读头向左移动，指向输入字符的前一个字符。?2?如果??q，a?＝?p，R?表示在读入a从状态q转移到状态p，并将读头向右移动，指向输入字符的下一个字符。?3?如果??q，a?＝?p，S?表示在读入a从状态q转移到状态p，读头保持在原位置不动。我们构造与之等价的FA*******************************************************************************