形式语言与自动机理论-蒋宗礼-参考答案VIP免费

精品文档。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 中至少含有两...