资源描述：
《第3章 作业及参考答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、1、针对DFAM1，(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接受过程的形式化：q01011001├1q3011001├10q111001├101q31001├1011q2001├1
2、0110q301├101100q11├1011001q3注意：谈及自动机形式化描述，一定是用五元组表示，将δ函数直接写出来2、构造识别下列语言的DFA（要求写出形式化描述，另外，写出设计过程对理清你的思维更有益）(3){x
3、x∈{0,1}+且x中不含形如00的子串}1001qtqsq1S10,1q00或：(对,但稍嫌麻烦)101001qtqsq1S1q00q２ ------------05级孙磊错解:10q0Sq1q2100,110q0Sq1q3100,1q20,10(x∈{0,1}*)10q0Sq110(不接受1,可接受000)(5){x
4、x∈{0,1}+且x中含形如10110的
5、子串}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
6、x∈{0,1}+且把x看成二进制数时，x模5与3同余，要求中当x为0时，
7、x
8、=1，
9、且x≠0时，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同余的等价类(x≠0)；所以，要构造的DFA为：M=({qs,q1,q2,q3,q4,q5,q
10、t},{0,1},δ,qs,{q3})状态转换函数δ定义如下：(0)在初始状态qs，δ(qs,0)=qt，δ(qs,1)=q1(1)当处于q1状态时，已读入的x=5n+1,n≥0由2x+0=5×2n+2，有δ(q1,0)=q2由2x+1=5×2n+3，有δ(q1,1)=q3(2)当处于q2状态时，已读入的x=5n+2,n≥0由2x+0=5×2n+4，有δ(q2,0)=q4由2x+1=5×(2n+1)+0，有δ(q2,1)=q5(3)当处于q3状态时，已读入的x=5n+3,n≥0由2x+0=5×(2n+1)+1，有δ(q3,0)=q1由2x+1=5×(2n+1)+2，有δ(q3,1)
11、=q2(4)当处于q4状态时，已读入的x=5n+4,n≥0由2x+0=5×(2n+1)+3，有δ(q4,0)=q3由2x+1=5×(2n+2)+4，有δ(q4,1)=q4(5)当处于q5状态时，已读入的x=5n,n>1由2x+0=5×2n+0，有δ(q5,0)=q5由2x+1=5×2n+1，有δ(q5,1)=q1(6)在陷阱状态qt，有δ(qt,0)=qt，δ(qt,1)=qt1q201qsSq1q4q300011110q5qt0,10(10){x
12、x∈{0,1}+且x中至少含两个1}01q0Sq1q2010,1或001S010,11------05级张士光错解:01q0Sq1q2
13、010,1------错误原因?10、构造识别下列语言的NFA(要求写出形式化描述)(2){x
14、x∈{0,1}+且x中含形如10110的子串}1q0Sq1q2q3q4q50,101100,1错解:1q0Sq1q2q3q4q501100,1qt0,100011-----用的是DFA思维另一不能算错的错误:设计DFA形式化描述时易犯的错误:δ(q3,1)=q2或δ(q3,1)={q2}(8){x
15、x∈{0,1}+且x的首字符和尾字符相同}11q1q0Sq2q30,1000
