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

第三章作业答案 1．已知DFA M1与M2如图3－18所示。 (敖雪峰 请分别给出它们在处理字符串1011001的过程中经过的状态序列。 请给出它们的形式描述。 图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 ( 陶文婧 ) （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 状态转移表为 状态 0 1 q0 q1 q2 q1 q3 q2 q2 q0 q4 q3 q1 q2 q4 q3 q4 （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是十进制非负数} （13）( （14）( ******************************************************************************* 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