有限自动机三章答案

1、第三章*1构造下列语言的 DFA( 陶文婧 02282085 )（1）0，1 *0，1（ 2）0，1 +S0 ，10 ， 1（3） x|x 0 ，1 +且 x 中不含（设置一个陷阱状态，一旦发现有00的串00 的子串，就进入陷阱状态）11S010,100（4） x|x0 ， 1 * 且 x 中不含 00 的串 （可接受空字符串，所以初始状态也是接受状态）11S0010,10（5） x|x0 ，1 +且 x 中含形如10110 的子串 010,1S10110001（6） x|x0 ，1 +且 x 中不含形如10110 的子串 （设置一个陷阱状态，一旦发现有00 的子串，就进入陷阱状态）1010,

2、1S,1011000（7） x|x0 ，1 +且当把 x 看成二进制时， x 模 5和 3同余，要求当x 为 0 时， |x|=1,且x0 时， x 的首字符为1 1.以 0 开头的串不被接受，故设置陷阱状态，当入陷阱状态DFA在启动状态读入的符号为0，则进2. 设置 7 个状态： 开始状态 qs,q0:除以 5 余 0 的等价类， q1： 除以 5 余 1 的等价类 ,q2:除以 5余 2 的等价类， q3:除以 5 余 3 的等价类， q4:除以 5 余 4 的等价类，接受状态qt3. 状态转移表为状态01q0q1q2q1q3q2q2q0q4q3q1q2q4q3q4q 0011q s0q

3、1q 2q 411100010q tq 30,1（ 8） x|x0 ， 1 +且 x 的第十个字符为 1（设置一个陷阱状态，一旦发现x 的第十个字符为0，进入陷阱状态）0,1S0,10,10,10,10,10,10,10,10,110,1（9） x|x0 ，1 +且 x 以 0 开头以（设置陷阱状态，当第一个字符为1 结尾1 时，进入陷阱状态）S0001110,1（10） x|x0 ， 1 +且 x 中至少含有两个 100,111010（11） x|x0 ， 1 +且如果 x 以 1 结尾，则它的长度为偶数；如果x 以 0 结尾，则它的长度为奇数 可将 0 ，1 +的字符串分为4 个等价类。q

4、0： 的等价类，对应的状态为终止状态q1:x 的长度为奇且以0 结尾的等价类q2： x 的长度为奇且以1 结尾的等价类q3: x 的长度为偶且以0 结尾的等价类q4: x 的长度为偶且以1 结尾的等价类q1q4q0100S011q3011q 2（12） x|x 是十进制非负数0S0， 1， 2， 3， 4，5，6，7，8，91， 2， 3， 4， 5，6，7，8，9.0， 1， 2， 3， 4，5，6，7，8，9（ 13）S（ 14）S* 2.(1)x x0,1且x中不含形如 00的子串1S100111(2) x x0,1 且x中含形如 10110的子串10110，100，1(3) x x0,

5、1且x中不含形如 10110的子串101100，10， 1(4) x x0,1 和x的倒数第 10个字符是 1，且以 01结尾 0，110，10，10， 10，1100，10，10， 1(5) x x0,1且x以0开头以1结尾0， 101(6) x x0,1且x中至少含有两个 10，10，10，1S110，1(7) x x0,1 * 且如果 x以 1结尾，则它的长度为偶数；如果以 0结尾，则它的长度为奇数1S0，10(8) x x 0,1且x的首字符和尾字符相等 00， 100110， 11(9) x xT x,0,1 0,100110,1*3.根据下列给定文法，构造相应的FA 。（敖雪峰02282068）(1) 文法 G1的产生式集合如下：G1: S a|AaA a|Aa|cA|BbB a|b|c|aB|Bb|Cb(2) 文法 G2的产生式集合如下：G2: S a|AaA a|Aa|Ac|BbB a|b|c|B