第3章 作业及参考答案

1、针对DFA M1，(1)请给出在处理字符串1011001的过程中经过的状态序列。解：经过的状态序列为：q0q3q1q3q2q3q1q3(2)请给出形式描述。争议：M1的形式化还是接受过程的形式化？解：M1的形式描述为M1=(q0,q1,q2,q3,0,1, q0, q3)其中定义为：(q0,0)= q1，(q0,1)= q3(q1,0)= q2，(q1,1)= q3(q2,0)= q3，(q2,1)= q0(q3,0)= q1，(q3,1)= q2接受过程的形式化：q010110011q301100110q111001101q310011011q200110110q301101100q111011001q3注意：谈及自动机形式化描述，一定是用五元组表示，将函数直接写出来2、构造识别下列语言的DFA（要求写出形式化描述，另外，写出设计过程对理清你的思维更有益）(3) x| x0,1+且x中不含形如00的子串1001qtqsq1S10,1q00或：(对, 但稍嫌麻烦)101001qtqsq1S1q00q-05级孙磊错解:10q0Sq1q2100,1 10q0Sq1q3100,1q20,10(x0,1*)10q0Sq110 (不接受1, 可接受000) (5) x| x0,1+且x中含形如10110的子串11q0Sq1q2q3q4q5001100010,1q0：起始状态，以及未读入1的状态；q1：读入了10110中第1个符号(1)的状态；q2：读入了10110中第2个符号(0)的状态；q3：读入了10110中第3个符号(1)的状态；q4：读入了10110中第4个符号(1)的状态；q5：读入了10110中第5个符号(0)的状态；易犯的错误: 状态转移时, 不考虑已接受一些字符后所处状态, 一味地转到开始状态，不利用阶段性成果，狗熊掰棒子！11q0Sq1q2q3q4q500110000,11(7) x| x0,1+且把x看成二进制数时，x模5与3同余，要求中当x为0时，|x|=1，且x0时，x首字符是1提示: 和P98例3-5属同一类型, 这种设计如不写清楚设计过程, 不能服人, 也不能反映你的设计方法.解：按题意，当x为0时，x的长度为1，即不能出现多于1个0的全0串；当x不为0时，必须以1开始。又由于0模5与3不同余，故在开始状态qs读入0，则直接进入陷阱状态qt，即(qs,0)= qt。其余状态为： q1：对应x模5与1同余的等价类； q2：对应x模5与2同余的等价类； q3：对应x模5与3同余的等价类(终止状态)； q4：对应x模5与4同余的等价类； q5：对应x模5与0同余的等价类(x0)；所以，要构造的DFA为：M=(qs,q1,q2,q3,q4,q5,qt,0,1, qs, q3)状态转换函数定义如下：(0)在初始状态qs，(qs,0)= qt，(qs,1)= q1(1)当处于q1状态时，已读入的x=5n+1, n0 由2x+0=52n+2，有(q1,0)= q2 由2x+1=52n+3，有(q1,1)= q3(2)当处于q2状态时，已读入的x=5n+2, n0 由2x+0=52n+4，有(q2,0)= q4 由2x+1=5(2n+1)+0，有(q2,1)= q5(3)当处于q3状态时，已读入的x=5n+3, n0 由2x+0=5(2n+1)+1，有(q3,0)= q1 由2x+1=5(2n+1)+2，有(q3,1)= q2(4)当处于q4状态时，已读入的x=5n+4, n0 由2x+0=5(2n+1)+3，有(q4,0)= q3 由2x+1=5(2n+2)+4，有(q4,1)= q4(5)当处于q5状态时，已读入的x=5n, n1 由2x+0=52n+0，有(q5,0)= q5 由2x+1=52n+1，有(q5,1)= q1(6)在陷阱状态qt，有(qt,0)= qt，(qt,1)= qt1q201qsSq1q4q300011110q5qt0,10(10) x| x0,1+且x中至少含两个1 01q0Sq1q2010,1或001S010,11-05级张士光错解:01q0Sq1q2010,1-错误原因?10、构造识别下列语言的NFA(要求写出形式化描述)(2) x| x0,1+且x中含形如10110的子串1q0Sq1q2q3q4q50,101100,1错解:1q0Sq1q2q3q4q501100,1qt0,100011-用的是DFA思维另一不能算错的错误: 设计DFA形式化描述时易犯的错误: (q3,1)= q2 或(q3,1)= q2 (8) x| x0,1+且x的首字符和尾字符相同11q1q0Sq2q30,1000,1q4或11q1q0Sq2q30,1000,1或(后面的这两个解更好!严格讲, 前两解不全对)11q1q0Sq2q30,1000,1q40,1-05级孙亮波或11q1q0Sq2q30,1000,10,1-05级孙磊11(1)、根据给定的NFA，构造与之等价的DFA状态说明状态输入字符012开始状态q0q0 q1q0 q2q0 q2q0 q1q0 q1 q3q0 q2q0 q2q0 q2q0 q1q0 q1 q2 q3q0 q1 q2终止状态q0 q1 q3q0 q1 q2 q3q0 q2 q3q0 q2q0 q1 q2q0 q1 q3q0 q1 q2 q3q0 q1 q2终止状态q0 q2 q3q0 q1 q2 q3q0 q1 q2 q3q0 q1 q2终止状态q0 q1 q2 q3q0 q1 q2 q3q0 q1 q2 q3q0 q1 q2形式化描述与状态转移图略.不合适的解法:(1)专门列出一个产生式Sq0(2)列出2Q中所有状态组, 没有必要; (2)状态组不用 括起来, 虽然本质上没有问题, 但可能忽略”状态集-状态组-单个状态”在思维上的转变.20、构造图3-20所给DFA对应的右线性文法（做左图）解：q00q1|1q3|1q10q0|1q3|1q30q1|1q1q20q3|1q1|0补充: 先将无用状态q2去掉再做 -05级张志辉, 岳宝提出不合适的解法: 把非终结符qi(原自动机中的状态)换为S,A,B等在文法中常见的符号, 抽象是去除表面的现象, 保留其实质所在, 如果在用的符号上都得费心思变一下才行, 对抽象能力培养不利(我以这个理由辩不该换符号, 其实你也可以同样的理由辩换了也无所谓, 但我觉得还是不换为好.)22(1)、根据下列所给文法，构造相应的FAG1：Sa|aAAa|aA|cA|bBBa|b|c|aB|bB|cB解：FA M=(S,A,B,Z, a,b,c,d, S, Z)，其中为d (S,a)= Z,Ad (A,a)= Z,Ad (A,c)= Ad (A,b)= Bd (B,a)= Z,Bd (B,b)= Z,Bd (B,c)= Z,B(可以画出状态转移图)不合适的解法: 同20题, 换符号错误写法：由Aa，(A,a)= Z由Aa，(A,a)= Z由AaA，(A,a)= A由AaA，(A,a)= A应该是：由Aa，Zd(A,a)由AaA，Ad(A,a)