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

第 三章作业答案 1．已知DFA M1 与M2 如图3－18 所示。 (敖雪峰 02282068) (1) 请分别给出它们在处理字符串 1011001 的过程中经过的状态序列。 (2) 请给出它们的形式描述。 0101001Sq0q1q2q31 01100q0q1q2q3101 图3－18 两个不同的DFA 解答：(1)M1在处理1011001的过程中经过的状态序列为q 0q 3q 1q 3q 2q 3q 1q 3; M2在处理1011001的过程中经过的状态序列为q 0q 2q 3q 1q 3q 2q 3q 1; (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 ，10S （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 的等价类，接受状态qt 3. 状态转移表为 状态 0 1 q0 q1 q2 q1 q3 q2 q2 q0 q4 q3 q1 q2 q4 q3 q4 11100,10q sq tq 1q 21q 010q 40q 3100 （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 中至少含有...