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