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

-18所示。(敖雪峰)请分别给出它们在处理字符串的过程中经过的状态序列。请给出它们的形式描述。图3-18两个不同的DFA解答:(1)M1在处理的过程中经过的状态序列为q0q3q1q3q2q3q1q3;M2在处理的过程中经过的状态序列为q0q2q3q1q3q2q3q1;(2)考虑到用形式语言表示,用自然语言似乎不是那么容易,所以用图上作业法把它们用正则表达式来描述:M1:[01+(00+1)(11+0)][11+(10+0)(11+0)]*M2:(01+1+000){(01)*+[(001+11)(01+1+000)]*}*******************************************************************************(陶文婧)(1){0,1}*(2){0,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}以0开头的串不被接受,故设置陷阱状态,当DFA在启动状态读入的符号为0,则进入陷阱状态设置7个状态:开始状态qs,q0:除以5余0的等价类,q1:除以5余1的等价类,q2:除以5余2的等价类,q3:除以5余3的等价类,q4:除以5余4的等价类,接受状态qt状态转移表为状态01q0q1q2q1q3q2q2q0q4q3q1q2q4q3q4(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:[e]的等价类,对应的状态为终止状态q1:x的长度为奇且以0结尾的等价类q2:x的长度为奇且以1结尾的等价类q3:x的长度为偶且以0结尾的等价类q4:x的长度为偶且以1结尾的等价类(12){x|x是十进制非负数}(13)F(14)e*******************************************************************************3(1)(张友坤)={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