下载文档原格式
1.写出表示下列语言的正则表达式。
（吴贤珺02282047）⑴{0, 1}*。
解：所求正则表达式为：(0+1)*。
⑵{0, 1}+。
解：所求正则表达式为：(0+1)+。
⑶{ x│x∈{0,1}+ 且x中不含形如00的子串 }。
解：根据第三章构造的FA，可得所求正则表达式为：1*(01+)*(01+0+1)。
⑷{ x│x∈{0,1}*且x中不含形如00的子串 }。
解：根据上题的结果，可得所求正则表达式为：ε+1*(01+)*(01+0+1)。
⑸{ x│x∈{0,1}+ 且x中含形如10110的子串 }。
解：所求正则表达式为：(0+1)*10110(0+1)*。
⑹ { x│x∈{0,1}+ 且x中不含形如10110的子串 }。
解：根据第三章的习题，接受x的FA为：要求该FA对应的正则表达式，分别以q0、q1、q2、q3、q4为终结状态考虑：q为终态时的正则表达式：(0*(11*0(10)*(ε+111*11*0(10)*)0)*)*q为终态时的正则表达式：0*1(1*(0(10)*111*1)*(0(10)*00*1)*)*1q为终态时的正则表达式：0*11*0((10)*(111*11*0)*(00*11*0)*)*2q为终态时的正则表达式：0*11*0(10)*1(11*11*0((10)*(00*11*0)*)*1)*3q为终态时的正则表达式：0*11*0(10)*11(1*(11*0((00*11*0)*(10)*)*11)*)*4将以上5个正则表达式用“+”号相连，就得到所要求的正则表达式。
⑺ { x│x∈{0,1}+ 且当把x看成二进制数时，x模5与3同余和x为0时，│x│=1且x≠0时，x的首字符为1}。
解：先画出状态转移图，设置5个状态q0、q1、q2、q3、q4，分别表示除5的余数是0、1、2、3、4的情形。
另外，设置一个开始状态q.由于要求x模5和3同余，而3模5余3,故只有q3可以作为终态。
Chapter 3 练习参考解答Exercise 3.1.1 写出下列语言的正规表达式:c） The set of strings of 0' s and1' s with at most one pair of consecutive 1' s.c）最多包含两个相继的 1 的所有0， 1 字符串的集合.参考解答：该题的翻译有二义性（Sorry ）.1）按原题意的解法对不包含相继的 1 的所有0， 1 字符串的集合，正规表达式可以为：1*（0+01）* 或（0+10 ）*1*；包含最多一对相继的1，正规表达式可以为：（0+10）*11（0+01）*；所以，结果正规表达式可以为：1*（0+01）* + （0+10 ）*11（0+01）2）若理解为11 可以出现多次的解法正规表达式可以为：1*（0+01+011 ）* 或（0+10+110）*1*；等等Exercise 3.1.2 写出下列语言的正规表达式:b） 0 的个数能够被 5 整除的所有0， 1 字符串的集合. 参考解答：该题问题不多.正规表达式可以为：（1*01*01*01*01*01* ）*Exercise 3.2.1（2）c）给出所有正规表达式R（i2j）, 并尽可能简化之.d）给出该自动机的语言的一个正规表达式.参考解答：该题问题反映较多的是关于正规表达式的简化. 本科程较侧重原理，技术方面不够细致，因此对于“最简“的正规表达式没有作明确的规定，也没有类似于命题演算中有关”范式“的讨论.同学们在做题时除了应用有关定律外， 还可以自己总结出一些规律，比如一个表达式的语言 R 是另一个表达式S 所代 表语言的一个子集，则对于 R+S 就可以消去R ，例如 +1*可以简化为1*.再 如，在已做过的习题中出现的公式，例如Exercise3.4.1(g)我们可以验证(汁R)*= R*，因此 (+1)*可以简化为1*.综合已阅过的作业，推荐以下结果：C) R (121)= 1*+1*0 ( +11*0)*11* = 1*+1*0(11*0)*11*R (1 2 = 1*0+1*0 ( ；+11*0)* ( ；+11*0) = 1*0(11*0)*R (123)= * +1*0 2+11*0)*0 = 1*0(11*0)*0R (221)= 11* + ( +11*0) ( +11*0)*11* = (11*0)*11* R (222)= +11*0 + ( +11*0) ( ；+11*0)* ( ；+11*0) = (11*0)*R (223)= 0 + ( +11*0) ( +11*0)*0 = (11*0)*0R (321) = * + 1 (<+11*0)*11* =1(11*0)*11*R (322)= 1 + 1 ( +11*0)* ( ；+11*0) =1(11*0)*R (323)= ； + 0 + 1 ( +11*0)* 0 = ； + 0 + 1(11*0)*0d)该自动机的语言的一个正规表达式为R (133) =1*0(11*0)*0 +1*0(11*0)*0 ( ； + 0 + 1(11*0)*0)* ( ； + 0 + 1(11*0)*0)=1*0(11*0)*0 (0 + 1(11*0)*0)*Exercise 3.2.3 使用状态消去技术，将如下 DFA 转化为一个正规表达式.参考解答：该题问题不多，状态消去的次序不同，结果形式上可能有所不同，但 相互之间是等价的.以下是一个解法:/1+0(01+10*11)*(00+10*10) Start 5结果正规表达式可以为：(1+0(01+10*11)*(00+10*10))* 原状态图:消去状态r :消去状态s :1Start 0Exercise 324 将下列正规表达式转化为带 &转移的NFA.b) (0+1)01 c) 00(0+1)*参考解答：若严格按照所介绍的算法构造，则结 果如下:b)Exercise 3.4.1验证下列包含正规表达式的等式 c) (RS) T = R (ST) .g)(+R)* = R* . 参考解答：c)将两个表达式具体化，将R 替换为a ，将S 替换为b.(RS)T 具体化为(ab)a ，R(ST)具体化为 a(ba)，而 L((ab)a)=L(a(ba))={abc}， 所以原等式成立；g)将两个表达式具体化，将R 替换为a.(+R)* 具体化为(；+a)*，R*具体化为 a*，而 L(( +a)*)=L(a*)={ ,a ,aa,aaa,…， (注：严格证明L(( ；+a)*)=L(a*)，可以在归纳证明：对任意k>=0，{；，a}k ={a}k 的基础上进行)，所以原等式成立;Exercise 342证明或否证下列关于正规表达式的命题 b) (RS+R)*R = R (SR+R)*.d) (R+S)*S = (R*S)* .Start参考解答：b)将两个表达式具体化，将R替换为a,将S替换为b.(RS+R)*R 具体化为(ab+a)*a，R (SR+R)*具体化为a(ba+a)*，可以证明L((ab+a)*a)=L(a(ba+a)*) (注：同上，可以先归纳证明：对任意k>=0，{ab，a}k{a}={a}{ba ，a}k，而由连接运算对-运算的分配律，—k —k 可知L((ab+a)*a)= *0,1,2, -({ab，a} {a}), L(a(ba+a)*)= k=o,1,2, ・({a}{ba，a})，由此证得L((ab+a)*a)=L(a(ba+a)*))，所以原等式成立；g)将两个表达式具体化，将R替换为a，将S替换为b.(R+S)*S 具体化为(a+b)*b，(R*S)* 具体化为(a*b)*，由于〉L((a*b)*)，而>■' L((a*b)*)，所以原等式不成立。
形式语言与自动机蒋宗礼答案形式语言与自动机蒋宗礼答案【篇一：形式语言第四章参考答案(蒋宗礼)】p> 解：所求正则表达式为：(0+1)*。
+⑵ {0, 1}。
解：所求正则表达式为：(0+1)+。
⑶ { x│x∈{0,1}且x中不含形如00的子串 }。
解：根据第三章构造的fa，可得所求正则表达式为：1*(01+)*(01+0+1)。
⑷ { x│x∈{0,1}*且x中不含形如00的子串 }。
++ +q1为终态时的正则表达式：0*1(1*(0(10)*111*1)*(0(10)*00*1)*)* q2为终态时的正则表达式：0*11*0((10)*(111*11*0)*(00*11*0)*)*q3为终态时的正则表达式：0*11*0(10)*1(11*11*0((10)*(00*11*0)*)*1)* q4为终态时的正则表达式：0*11*0(10)*11(1*(11*0((00*11*0)*(10)*)*11)*)* 将以上5个正则表达式用“+”号相连，就得到所要求的正则表达式。
⑺ { x│x∈{0,1}且当把x看成二进制数时，x模5与3同余和x为0时，│x│=1且x≠0时，x的首字符为1}。
解：先画出状态转移图，设置5个状态q0、q1、q2、q3、q4，分别表示除5的余数是0、1、2、3、4的情形。
另外，设置一个开始状态q.由于要求x模5和3同余，而3模5余3,故只有q3可以作为终态。
由题设，x=0时，│x│=1，模5是1，不符合条件，所以不必增加关于它的状态。
下面对每一个状态考虑输入0和1时的状态转移。
q: 输入1，模5是1，进入q1。
+q0: 设x=5n。
输入0，x=5n*2=10n，模5是0，故进入q0输入1，x=5n*2+1=10n+1，模5是1，故进入q1q1：设x=5n+1。
输入0，x=(5n+1)*2=10n+2，模5是2，故进入q2输入1，x=(5n+1)*2+1=10n+3，模5是3，故进入q3 q2：设x=5n+2。
形式语言与自动机答案蒋宗礼【篇一：形式语言第四章参考答案(蒋宗礼)】p> 解：所求正则表达式为：(0+1)*。
+⑵ {0, 1}。
解：所求正则表达式为：(0+1)+。
⑶ { x│x∈{0,1}且x中不含形如00的子串 }。
解：根据第三章构造的fa，可得所求正则表达式为：1*(01+)*(01+0+1)。
⑷ { x│x∈{0,1}*且x中不含形如00的子串 }。
++ +q1为终态时的正则表达式：0*1(1*(0(10)*111*1)*(0(10)*00*1)*)* q2为终态时的正则表达式：0*11*0((10)*(111*11*0)*(00*11*0)*)*q3为终态时的正则表达式：0*11*0(10)*1(11*11*0((10)*(00*11*0)*)*1)* q4为终态时的正则表达式：0*11*0(10)*11(1*(11*0((00*11*0)*(10)*)*11)*)*将以上5个正则表达式用“+”号相连，就得到所要求的正则表达式。
⑺ { x│x∈{0,1}且当把x看成二进制数时，x模5与3同余和x为0时，│x│=1且x≠0时，x的首字符为1}。
解：先画出状态转移图，设置5个状态q0、q1、q2、q3、q4，分别表示除5的余数是0、1、2、3、4的情形。
另外，设置一个开始状态q.由于要求x模5和3同余，而3模5余3,故只有q3可以作为终态。
由题设，x=0时，│x│=1，模5是1，不符合条件，所以不必增加关于它的状态。
下面对每一个状态考虑输入0和1时的状态转移。
q: 输入1，模5是1，进入q1。
+q0: 设x=5n。
输入0，x=5n*2=10n，模5是0，故进入q0输入1，x=5n*2+1=10n+1，模5是1，故进入q1q1：设x=5n+1。
输入0，x=(5n+1)*2=10n+2，模5是2，故进入q2输入1，x=(5n+1)*2+1=10n+3，模5是3，故进入q3 q2：设x=5n+2。
1•写出表示下列语言的正则表达式。
(吴贤环02282047)(1){0, 1}*。
解：所求正则表达式为：(0+1)*。
(2){0, 1}\解：所求正则表达式为:(0+1几(3){ x | xe {0, 1甘且x中不含形如00的子串}o解：根据第三章构造的FA,可得所求正则表达式为：1*(0广)*(01+0+1)。
(4){ X I xe {0, 1}*且X中不含形如00的子串}。
解：根据上题的结果，可得所求正则表达式为：£+1*(0广)*(01+0+1)。
(5){ x | xG{0, 1}+且x中含形如10110的子串}。
解：所求正则表达式为:(0+1)*10110(0+1)*。
(6){ x | xe {0, 1}^且x中不含形如10110的子串}。
解：根据第三章的习题，接受x的FA为：要求该FA对应的正则表达式，分别以q。
、q】、q2> q3> q(为终结状态考虑：qo为终态时的正则表达式:(0*( 11 *0( 10)*( £ +111*11*0(10)*)0)*)*qi 为终态时的正则表达式:0*1(1*(0(10)*111*1)*(0(10)*00*1)*)* q?为终态时的正则表达式:0* 11*0(( 10)*( 111*11 *0)*(00* 11 *0)*)*q3 为终态时的正则表达式:0* 11 *0( 10)* 1 (11 * 11 *0(( 10)*(00* 11 *0)*)* 1 )*q，i 为终态时的正则表达式:0* 11 *0( 10)* 11 (1 *( 11 *0((00* 11 *0)*( 10)*)* 11)*)* 将以上5个正则表达式用“ + ”号相连，就得到所要求的正则表达式。
(7){ x | xe {0, 1广且当把X看成二进制数时,x模5与3同余和X为0时，I x I =1 且xHO时,x的首字符为1}。
解：先画出状态转移图，设置5个状态q。
形式语言与自动机形式语言与自动机理论-蒋宗礼-第三章参考答案导读：就爱阅读网友为您分享以下“形式语言与自动机理论-蒋宗礼-第三章参考答案”的资讯，希望对您有所帮助，感谢您对的支持!因此我们只需要证明对任何的2NFA M1?(Q1,?,?1,F1,q0)，都存在FAM2?(Q2,?,?2,F2,q0)与之等价。
对于任何的2NFA M1?(Q1,?,?1,F1,q0)，构造FA M2?(Q2,?,?2,F2,q0)，按三个方式构造?2：1．如果q?Q1,a??,?1(q,a)?{p,R},则?2(q,a)?p；2．如果q?Q1,a??,?1(q,a)?{p,S},则如果??1(p,a)?{o,R}，则?2(q,a)?o；如果??1(p,a)?{o,S}，则重复第二步；如果??1(p,a)?{o,L}，则对于集合A = {r|b?Q1,?1(r,b)?(o,R)}，?2(q,a)?r,r?A。
3．如果q?Q1,a??,?1(q,a)?{p,L},则设集合 A = {r|b?Q1,?1(r,b)?(p,R)}，?2(q,a)?r,r?A*************************************************** ****************************28．证明定理3-8：Moore机与Mealy机等价（郭会02282015）证明：不妨设Moore机M1=(Q1,?,?,?1,?1,q01)，Mealy机M2=(Q2,?,?,?2,?2,q02)，则根据Moore机和Mealy机等价的定义知，必须证明：T1(x)??1(q0)T2(x),其中T1(x)和T2(x)分别表示M1和M2关于x的输出。
??Moore机M1,?Mealy机M2,使M2与M1等价（1）构造M2，?2??1,q02?q01,Q2?Q1?q?Q1?{q01},?1(q)?a,?q'?Q1且?b??,?1(q',b)=q,就构造?2（q',b）=a（2）证明?x??*，?1(q0)T2(x)?T1(x)不妨设x?x1x2……xn,则?i?N,(i?1,2……n)则M1的输出为:T1(x)??1(q0)?1(?1(q0,x1))……?1(?1((…?1(q0,x1)，x2)…)，xn)由题意可知?1(q0,x1)，?1(?1(q0,x1),x2)，…，?1(……?1 (?1(q0,x1),x2) xn) 均为Moore机中的状态，由（1）中的构造假设知，M2的输出为：T2(x)??2(q0,x1)?2(?2(q0,x1),x2)…?2(……?2(?2(q0,x1),x2) ? ?1(q0,x1)?1(?1(q0,x1),x2)…?1(……?1(?1(q0,x1),x2) xn) xn) ?T1(x)??1(q0)T2(x)??Mealy机M2,?Moore机M1,使M1与M2等价（1）构造M1，q01?q02Q1?Q2?{qij|??2(qi,a)?qj,其中qi,qj?Q2,a??}?1?{?|?(qi,a)?qij,?(qij,?)?qj其中?2(qi,a)?qj}?1?{?|?1(qi,a)?qij,?1(qij,?)?qj,?(qij)??2(qi,a) }（2）证明?x??*，T1(x)＝?1(q0)T2(x)不妨设x?x1x2……xn,则?i?N,(i?1,2……n)则M1的输出为:T2(x)??2(?2(q0,x1))……?2(?2((…?2(q0,x1)，x2)…)，xn) 由题意可知?2(q0,x1)，?2(?2(q0,x1),x2)，…，?2(……?2 (?2(q0,x1),x2) xn) 均为Mealy机中的状态，由（1）中的构造假设知，M1的输出为：T1(x)??1(q0)?1(?2(q0,x1))?1(?1(q0,x1),x2)…?1(……?1(?1(q 0,x1),x2) xn)??1(q0)?2(?2(q0,x1))……?2(?2((…?2(q0,x1)，x2)…)，xn) ?T1(x)??1(q0)T2(x)综上所述，Moore机与Mealy机等价第三章作业答案1．已知DFA M1与M2如图3－18所示。
第三章作业答案1．已知DFA M1与M2如图3－18所示。
(敖雪峰 02282068)(1) 请分别给出它们在处理字符串1011001的过程中经过的状态序列。
(2) 请给出它们的形式描述。
Sq q1图3－18 两个不同的DFA解答：(1)M1在处理1011001的过程中经过的状态序列为q 0q 3q 1q 3q 2q 3q 1q 3; M2在处理1011001的过程中经过的状态序列为q 0q 2q 3q 1q 3q 2q 3q 1;(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}*，1（2）{0，1}+，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 }1.以0开头的串不被接受，故设置陷阱状态，当DFA在启动状态读入的符号为0，则进入陷阱状态2.设置7个状态：开始状态q s,q0:除以5余0的等价类，q1：除以5余1的等价类,q2:除以5余2的等价类，q3:除以5余3的等价类，q4:除以5余4的等价类，接受状态q t（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：[ε]的等价类，对应的状态为终止状态q1:x的长度为奇且以0结尾的等价类q2：x的长度为奇且以1结尾的等价类q3: x的长度为偶且以0结尾的等价类q4: x的长度为偶且以1结尾的等价类（12）{x|x是十进制非负数}5，6，7，8，94，9（13）Φ（14）ε*******************************************************************************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的子串}Set(q4)={x | x∈∑*,并且x中含形如1011的子串}Set(q5)={x | x∈∑*,并且x中含形如10110的子串}(6)∑={0,1}Set(q0)= {ε}Set(q1)={x | x∈{0+}}Set(q2)={x | x∈∑*,并且x中不含形如10110的子串而且x中含有1} Set(q3)={x | x∈∑*,并且x中不含形如10110的子串而且x中含有1} (7)∑={0,1}Set(qs)= {ε}Set(qe)= {0}Set(q1)={x | x∈∑+,并且把x看成二进制数时，x% 5=1}Set(q2)={x | x∈∑+,并且把x看成二进制数时，x% 5=2}Set(q3)={x | x∈∑+,并且把x看成二进制数时，x% 5=3}Set(q4)={x | x∈∑+,并且把x看成二进制数时，x% 5=4}Set(q0)={x | x∈∑+,并且把x看成二进制数时，x% 5=0并且x不为0} (8)M={Q, ∑,δ,q0,F}Q={q0,q1,q2, (10)∑={0,1}当0<=i<=8时候，δ(q i,0)= δ( q i,1)=q（i+1）δ( q 9,1)=q10δ(q 10,0)= δ( q 10,1)=q10F={ q 10}Set(q0)= {ε}Set(q1)= {0,1}Set(q2)={x | x∈∑+,并且|x|=2}Set(q3)={x | x∈∑+,并且|x|=3}Set(q4)={x | x∈∑+,并且|x|=4}Set(q5)={x | x∈∑+,并且|x|=5}Set(q6)={x | x∈∑+,并且|x|=6}Set(q7)={x | x∈∑+,并且|x|=7}Set(q8)={x | x∈∑+,并且|x|=8}Set(q9)={x | x∈∑+,并且|x|=9}Set(q10)={x | x∈∑+,并且x的第十个字符是1}(9) M={Q, ∑,δ,q0,F}Q={q0,q1,q2 }∑={0,1}δ(q 0,0)=q1δ(q 1,0)= q1δ(q 1,1)= q2δ(q 2,1)= q2δ(q 2,0)= q1F={ q 2}Set(q0)= {ε}Set(q1)={x | x∈∑+,并且x以0开头以0结尾}Set(q2)={x | x∈∑+,并且x以0开头以1结尾}(10) M={Q, ∑,δ,q0,F}Q={q0,q1,q2 }∑={0,1}δ(q 0,0)=q0δ(q 0,1)=q1δ(q 1,0)= q1δ(q 1,1)= q2δ(q 2,1)= q2δ(q 2,0)= q2F={ q 2}Set(q0)= {0}*Set(q1)={x | x∈∑+,并且x中只有一个1 } Set(q2)={x | x∈∑+,并且x至少有俩个1} (11) M={Q, ∑,δ,q0,F}Q={q0,q1,q2 , q3,q4 }∑={0,1}δ(q 0,0)=q1δ(q 0,1)=q4δ(q 1,0)= q3δ(q 1,1)= q2δ(q 2,1)= q4δ(q 2,0)= q1δ(q 3,0)= q1δ(q 3,1)= q4δ(q 4,1)= q2δ(q 4,0)= q3F={ q 0 ,q 1 ,q 2}Set(q0)= {ε}Set(q1)={x | x∈∑+,以0结尾，长度为奇数} Set(q2)={x | x∈∑+,以1结尾，长度为偶数} Set(q3)={x | x∈∑+,以0结尾，长度为偶数} Set(q4)={x | x∈∑+,以1结尾，长度为奇数} (12)M={Q, ∑,δ,q0,F}Q={q0,q1,q2,q3,q4}∑={.,0,1,2, (9)F={q1,q2,q4}δ(q 0,0)=q1δ(q 0,1|2|3|4|5|6|7|8|9)=q2δ(q 1, . )=q2δ(q 2,0|1|2|3|4|5|6|7|8|9)=q2δ(q 2, . )=q3δ(q 3,0|1|2|3|4|5|6|7|8|9)=q4δ(q 4,0|1|2|3|4|5|6|7|8|9)=q4Set(q0)= {ε}Set(q1)={0 }Set(q2)={十进制正整数}Set(q3)={十进制非负整数后面接个小数点. }Set(q4)={十进制正小数}（13）Set(q0)= {ε} Set(q0)=∅ （14）Set(q0)= {ε}******************************************************************************* 4 在例3-6中，状态采用]...[21n a a a q 的形式，它比较清楚地表达出该状态所对应的记忆内容，给我们解决此问题带来了很大的方便，我们是否可以直接用]...[21n a a a 代替]...[21n a a a q 呢？如果能，为什么？如果不能，又是为什么？从此问题的讨论，你能总结出什么来？ （唐明珠 02282084） 答：我认为能够直接用]...[21n a a a 代替]...[21n a a a q ，因为在例3-6中，]...[21n a a a q 只是一种新的表示方法，用来表示状态存储的字符，这样就省去了在δ中逐一给出每一个具体的输入字符和状态的定义。
它的作用在于使FA 中状态定义更加简洁。
得到结论：在今后描述FA 时，应该根据具体的情况，使用适当的方法。
******************************************************************************* 5．试区别FA 中的陷阱状态和不可达状态。
（吴贤珺 02282047） 解：⑴ 陷阱状态（课本97页）：指在其它状态下发现输入串不可能是该FA 所识别的句子时所进入的状态。
FA 一旦进入该状态，就无法离开，并在此状态下，读完输入串中剩余的字符。
⑵ 不可达状态（课本108页）：指从FA 的开始状态出发，不可能到达的状态。
就FA的状态转移图来说，就是不存在从开始状态对应的顶点出发，到达该状态对应顶点的路径。
⑶ 从两者的定义可见：相对于不可达状态来说，陷阱状态是可达的。
但是，它们都是状态转移图中的非正常状态。
如果从状态转移图中的状态引一条弧到不可达状态，同时不可达状态所有的移动都是到自身。
这样，不可达状态就变成了陷阱状态。
****************************************************************************** 注：此题目有问题，可以将题设改为：x 中0和1个数相等且交替出现6．证明：题目有不严密之处，图中给出DFA 与题目中的语言L （M ）={x|x x ∈{0，1}+ 且x 中0的个数和1的个数相等}不完全对应，首先图中的DFA 可接受空字符串，而L （M ）不接受，其次，对于有些句子，例如1100，L （M ）可以接受，但DFA 不接受 （1）根据图中的DFA 可看出，右下角的状态为陷阱状态，所以去除陷阱状态 （2）由DFA 可构造出与其对应的右线性文法： （刘钰 02282083）01|110|000,0101|0110|10S A A S S BB S S A S S B S S S S →→→→→→→→将1S,1代入；代入得由此可以看出该文法接受的语言为L={(10|01)*},显然01或10分别是作为整体出现的，所以L(M)中0和1的个数相等。
