精品文档。1欢迎下载第三章作业答案1.已知 DFA M1与 M2如图 3-18 所示。 (敖雪峰 02282068) (1)请分别给出它们在处理字符串1011001 的过程中经过的状态序列。(2)请给出它们的形式描述。0101001Sq0q1q2q3101100q0q1q2q3101图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 ( 陶文婧 02282085 ) (1){0 ,1}*0,1(2){0 ,1}+ 0,10,1S(3){x|x{0 , 1}+且 x 中不含 00 的串 } (设置一个陷阱状态,一旦发现有00 的子串,就进入陷阱状态)精品文档。2欢迎下载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,q 0:除以 5 余 0 的等价类, q1:除以 5 余 1 的等价类 ,q 2:除以5 余 2 的等价类, q3: 除以 5 余 3 的等价类, q4:除以 5 余 4 的等价类,接受状态qt3.状态转移表为状态0 1 q0 q1q2q1q3q2q2q0q4q3q1q2精品文档。3欢迎下载q4q3q411100,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 中至少含有两...