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

第三章作业答案
1．已知DFA M1与M2如图3－18所示。 (敖雪峰 02282068)
请分别给出它们在处理字符串1011001的过程中经过的状态序列。
请给出它们的形式描述。

图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}*
（2）{0，1}+

（3）{x|xÎ{0，1}+且x中不含00的串}
（设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态）

（4）{ x|xÎ{0，1}*且x中不含00的串}
（可接受空字符串，所以初始状态也是接受状态）
（5）{x|xÎ{0，1}+且x中含形如10110的子串}
（6）{x|xÎ{0，1}+且x中不含形如10110的子串}
（设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态）

（7）{x|xÎ{0，1}+且当把x看成二进制时，x模5和3同余，要求当x为0时，|x|=1,且x¹0时，x的首字符为1 }
以0开头的串不被接受，故设置陷阱状态，当DFA在启动状态读入的符号为0，则进入陷阱状态
设置7个状态：开始状态qs,q0:除以5余0的等价类，q1：除以5余1的等价类,q2:除以5余2的等价类，q3:除以5余3的等价类，q4:除以5余4的等价类，接受状态qt
状态转移表为
状态
0
1
q0
q1
q2
q1
q3
q2
q2
q0
q4
q3
q1
q2
q4
q3
q4
（8）{x|xÎ{0，1}+且x的第十个字符为1}
（设置一个陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态）
（9）{x|xÎ{0，1}+且x以0开头以1结尾}
（设置陷阱状态，当第一个字符为1时，进入陷阱状态）


（10）{x|xÎ{0，1}+且x中至少含有两个1}

（11）{x|xÎ{0，1}+且如果x以1结尾，则它的长度为偶数；如果x以0结尾，则它的长度为奇数}
可将{0，1}+的字符串分为4个等价类。
q0： [e]的等价类，对应的状态为终止状态
q1:x的长度为奇且以0结尾的等价类
q2：x的长度为奇且以1结尾的等价类
q3: x的长度为偶且以0结尾的等价类
q4: x的长度为偶且以1结尾的等价类
（12）{x|x是十进制非负数}
（13）F
（14）e
*******************************************************************************
3 (1) （张友坤02282061）
={0,1}
Set(q0)={x | x * }
(2)
={0,1}
Set(q0)=
Set(q1)={x | x + }
（3）
={0,1}
Set(q0)=
Set(q1)={x | x +并且x中不含形如00的子串 }
Set(q2)={x | x +并且x中不含形如00的子串 }
(4)
={0,1}
Set(q0)={x | x *并且x中不含形如00的子串 }
Set(q1)={x | x *并且x中不含形如00的子串 }
(5)
={0,1}
Set(q0)= {x | x *,并且x{0}*或者x中含形如100的子串 }
Set(q1)={x | x *,并且x中含形如1的子串}
Set(q2)={x | x *,并且x中含形如10的子串 }
Set(q3)={x | x *,并且x中含形如101的子