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

第三章作业答案1．已知DFAM1与M2如图3－18所示。(敖雪峰02282068)(1)请分别给出它们在处理字符串1011001的过程中经过的状态序列。(2)请给出它们的形式描述。0101001Sq0q1q2q3101100q0q1q2q3101图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}*0，1（2）{0，1}+0，10，1S（3）{x|x{0，1}+且x中不含00的串}（设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态）11S00100,1（4）{x|x{0，1}*且x中不含00的串}（可接受空字符串，所以初始状态也是接受状态）11S00100,1（5）{x|x{0，1}+且x中含形如10110的子串}1S00100,110101（6）{x|x{0，1}+且x中不含形如10110的子串}（设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态）1S00100,1,10101（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的等价类，接受状态qt3.状态转移表为状态01q0q1q2q1q3q2q2q0q4q3q1q2q4q3q411100,10qsqtq1q21q010q40q3100（8）{x|x{0，1}+且x的第十个字符为1}（设置一个陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态）1S0,10,10,10,10,110,0,10,10,10,10,1（9）{x|x{0，1}+且x以0开头以1结尾}（设置陷阱状态，当第一个字符为1时，进入陷阱状态）1S01100,10（10）{x|x{0，1}+且x中至少含有两个1}1100,1010（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结尾的等价类11S0q1q2q0q40q310011（12）{x|x是十进制非负数}S01，2，3，4，5，6，7，8，90，1，2，3，4，5，6，7，8，9.0，1，2，3，4，5，6，7，8，9（13）S（14）S*******************************************************************************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中，状态采用]...[21naaaq的形式，它比较清楚地表达出该状态所对应的记忆内容，给我们解决此问题带来了很大的方便，我们是否可以直接用]...[21naaa代替]...[21naaaq呢？如果能，为什么？如果不能，又是为什么？从此问题的讨论，你能总结出什么来？（唐明珠02282084）答：我认为能够直接用]...[21naaa代替]...[21naaaq，因为在例3-6中，]...[21naaaq只是一种新的表示方法，用来表示状态存储的字符，这样就省去了在中逐一给出每一个具体的输入字符和状态的定义。它的作用在于使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）01|110|000,0101|0110|10SAASSBBSSASSBSSSS将1S,1代入；代入得由此可以看出该文法接受的语言为L={(10|01)*},显然01或10分别是作为整体出现的，所以L(M)中0和1的个数相等。******************************************************************************7．设DFAM=),,,,(0FqQ，证明：对于)),,((),(,,,*yxqxyqQqyx注：采用归纳证明的思路证明：(周期律02282067)首先对y归纳，对任意x来说，|y|=0时，即y=根据DFA定义,),(qq)),,(()),,((),(),(yxqxqxqxyq,故原式成立。当|y|=n时，假设原式成