形式语言第三章参考答案

第三章作业答案

1．已知DFA M1与M2如图3－18所示。 (敖雪峰 02282068)

(1) 请分别给出它们在处理字符串1011001的过程中经过的状态序列。 (2) 请给出它们的形式描述。

q0S0q1q00q111010101110q2q30q2q3

图3－18 两个不同的DFA

解答：(1)M1在处理1011001的过程中经过的状态序列为q0q3q1q3q2q3q1q3;

M2在处理1011001的过程中经过的状态序列为q0q2q3q1q3q2q3q1;

(2)考虑到用形式语言表示,用自然语言似乎不是那么容易,所以用图上作业法把它们用正则表达式来描述:

M1: [01+(00+1)(11+0)][11+(10+0)(11+0)]*

10

M2: (01+1+000){(01)*+[(001+11)(01+1+000)]*}

******************************************************************************* 2．构造下列语言的DFA ( 陶文婧 02282085 )

*

（1）{0，1}

0，1（2）{0，1}

S+

0，10，1

（3）{x|x?{0，1}+且x中不含00的串}

（设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态）

S0110100,1

*

（4）{ x|x?{0，1}且x中不含00的串}

（可接受空字符串，所以初始状态也是接受状态）

S0110100,1

（5）{x|x?{0，1}且x中含形如10110的子串}

+

010,1010110S0+

1

（6）{x|x?{0，1}且x中不含形如10110的子串}

（设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态）

100101100,1S0,1

（7）{x|x?{0，1}+且当把x看成二进制时，x模5和3同余，要求当x为0时，|x|=1,且x?0

时，x的首字符为1 } 1. 以0开头的串不被接受，故设置陷阱状态，当DFA在启动状态读入的符号为0，则进

入陷阱状态 2. 设置7个状态：开始状态qs,q0:除以5余0的等价类，q1：除以5余1的等价类,q2:除以5余2的等价类，q3:除以5余3的等价类，q4:除以5余4的等价类，接受状态qt 3. 状态转移表为 状态 q0 q1 q2 q3 0 q1 q3 q0 q1 1 q2 q2 q4 q2 q4

q3 q4 q00110qs1q1101q21q4000qt0,1q3

（8）{x|x?{0，1}且x的第十个字符为1}

（设置一个陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态）

0,1+

S0,10,10,10,10,10,10,10,10,110,1（9）{x|x?{0，1}+且x以0开头以1结尾}

（设置陷阱状态，当第一个字符为1时，进入陷阱状态）

00110,10S1

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

00,111010

+

（11）{x|x?{0，1}且如果x以1结尾，则它的长度为偶数；如果x以0结尾，则它的长度

为奇数}

可将{0，1}的字符串分为4个等价类。 q0： [?]的等价类，对应的状态为终止状态 q1:x的长度为奇且以0结尾的等价类 q2：x的长度为奇且以1结尾的等价类 q3: x的长度为偶且以0结尾的等价类 q4: x的长度为偶且以1结尾的等价类

+

q1q0S110010q40q311q2（12）{x|x是十进制非负数}

0

S1，2，3，4，5，6，7，8，90，1，2，3，4，5，6，7，8，9.0，1，2，3，4，5，6，7，8，9

（13）?

S

（14）?

S

*******************************************************************************

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)

本文来源：https://www.bwwdw.com/article/103t.html