资源描述：
《形式语言与自动机理论-蒋宗礼-第三章参考答案》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第三章作业答案1．已知DFAM1与M2如图3－18所示。(敖雪峰02282068)(1)请分别给出它们在处理字符串1011001的过程中经过的状态序列。(2)请给出它们的形式描述。图3－18两个不同的DFA解答：(1)M1在处理1011001的过程中经过的状态序列为q0q3q1q3q2q3q1q3;M2在处理1011001的过程中经过的状态序列为q0q2q3q1q3q2q3q1;(2)考虑到用形式语言表示,用自然语言似乎不是那么容易,所以用图上作业法把它们用正则表达式来描述:M1:[01+(00+1)(11+0)][11+(10+0)(11+0)]*M2:(01+
2、1+000){(01)*+[(001+11)(01+1+000)]*}*******************************************************************************2．构造下列语言的DFA(陶文婧02282085)（1）{0，1}*（2）{0，1}+（3）{x
3、xÎ{0，1}+且x中不含00的串}（设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态）（4）{x
4、xÎ{0，1}*且x中不含00的串}（可接受空字符串，所以初始状态也是接受状态）（5）{x
5、xÎ{0，1}+且x中含形如10110的子串}
6、（6）{x
7、xÎ{0，1}+且x中不含形如10110的子串}（设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态）（7）{x
8、xÎ{0，1}+且当把x看成二进制时，x模5和3同余，要求当x为0时，
9、x
10、=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.状态转移表为状态01q0q1q2q1q3q2q2q0q4q3q
11、1q2q4q3q4（8）{x
12、xÎ{0，1}+且x的第十个字符为1}（设置一个陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态）（9）{x
13、xÎ{0，1}+且x以0开头以1结尾}（设置陷阱状态，当第一个字符为1时，进入陷阱状态）（10）{x
14、xÎ{0，1}+且x中至少含有两个1}（11）{x
15、xÎ{0，1}+且如果x以1结尾，则它的长度为偶数；如果x以0结尾，则它的长度为奇数}可将{0，1}+的字符串分为4个等价类。q0：[e]的等价类，对应的状态为终止状态q1:x的长度为奇且以0结尾的等价类q2：x的长度为奇且以1结尾的等价类q3:x的长度为偶且以0结尾的等价
16、类q4:x的长度为偶且以1结尾的等价类（12）{x
17、x是十进制非负数}（13）F（14）e*******************************************************************************3(1)（张友坤02282061）={0,1}Set(q0)={x
18、x*}(2)={0,1}Set(q0)=Set(q1)={x
19、x+}（3）={0,1}Set(q0)=Set(q1)={x
20、x+并且x中不含形如00的子串}Set(q2)={x
21、x+并且x中不含形如00的子串}(4)={0,1}Set(q0)={x
22、x*
23、并且x中不含形如00的子串}Set(q1)={x
24、x*并且x中不含形如00的子串}(5)={0,1}Set(q0)={x
25、x*,并且x{0}*或者x中含形如100的子串}Set(q1)={x
26、x*,并且x中含形如1的子串}Set(q2)={x
27、x*,并且x中含形如10的子串}Set(q3)={x
28、x*,并且x中含形如101的子串}Set(q4)={x
29、x*,并且x中含形如1011的子串}Set(q5)={x
30、x*,并且x中含形如10110的子串}(6)={0,1}Set(q0)={}Set(q1)={x
31、x{0+}}Set(q2)={x
32、x*,并且x中不含形如10
33、110的子串而且x中含有1}Set(q3)={x
34、x*,并且x中不含形如10110的子串而且x中含有1}(7)={0,1}Set(qs)={}Set(qe)={0}Set(q1)={x
35、x+,并且把x看成二进制数时，x%5=1}Set(q2)={x
36、x+,并且把x看成二进制数时，x%5=2}Set(q3)={x
37、x+,并且把x看成二进制数时，x%5=3}Set(q4)={x
38、x+,并且把x看成二进制数时，x%5=4}Set(q0)={x
39、x+,并且把x看成二进制数时，x%5=0并且x不为0}(8)M={Q,,,q0,F}Q={q0,q1,q2,…q10}={0,1
40、}当0<=
