资源描述：
《形式语言与自动机理论试题答案解析new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、形式语言与自动机理论试题答案解析一、按要求完成下列填空1.给出集合{Φ,{Φ}}和集合{ε,0,00}的幂集（2x4）(1){Φ,{Φ},{{Φ}},{Φ,{Φ}}}(2){Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{ε,0,00}}2.设∑={0,1},请给出∑上的下列语言的文法（2x5）(1)所有包含子串01011的串S→X01011YX→ε
2、0X
3、1XY→ε
4、0Y
5、1Y(2)所有既没有一对连续的0，也没有一对连续的1的串A→ε
6、A’
7、A”A’→0
8、01
9、01A’A”→1
10、10
11、10A”3.构造识别下列语言的DFA2x6(1){x
12、
13、xÎ{0，1}+且x以0开头以1结尾}（设置陷阱状态，当第一个字符为1时，进入陷阱状态）(2){x
14、xÎ{0，1}+且x的第十个字符为1}（设置一个陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态）二、判断（正确的写T，错误的写F）5x21.设和是集合{a,b,c,d,e}上的二元关系，则(T)任取(x.,y),其中x,y，使得。2.对于任一非空集合A，Φ(T)3.文法G：SA
15、ASAa
16、b
17、c
18、d
19、e
20、f
21、g是RG(F)4.3型语言2型语言1型语言0型语言(F)5.s（rs+s）r=rrs（rrs）(F)不成立，假设r,s分别是表示语言R，S的正则表达式，
22、例如当R={0}，S={1},L(s(rs+s)*r)是以1开头的字符串，而L(rr*s(rr*s)*)是以0开头的字符串.L(s(rs+s)*r)L(rr*s(rr*s)*)所以s(rs+s)*rrr*s(rr*s)*,结论不成立三、设文法G的产生式集如下，试给出句子aaabbbccc的至少两个不同的推导（12分）。bB→bbCB→BCbC→bccC→cc推导一：S=>aSBC=>aaSBCBC=>aaaBCBCBC=>aaabCBCBC=>aaabBCCBC=>aaabbCCBC=>aaabbCBCC=>aaabbBCCC=>aaabbbCCC=>aaabb
23、bcCC=>aaabbbccC=>aaabbbccc推导二：S=>aSBC=>aaSBCBC=>aaaBCBCBC=>aaaBBCCBC=>aaaBBCBCC=>aaabBCBCC=>aaabbCBCC=>aaabbBCCC=>aaabbbCCC=>aaabbbcCC=>aaabbbccC=>aaabbbccc四、判断语言{
24、n>=1}是否为RL，如果是，请构造出它的有穷描述(FA,RG或者RL）；如果不是，请证明你的结论（12分）解：设L={
25、n>=1}。假设L是RL，则它满足泵引理。不妨设N是泵引理所指的仅依赖于L的正整数，取Z=显然，Z∈L。按照泵引理所述
26、，必存在u，v，w。由于
27、uv
28、<=N,并且
29、v
30、>=1，所以v只可能是由0组成的非空串。不妨设v=，k>=1此时有u=，w=从而有uvw=当i=2时，有uvw=又因为k>=1,所以N+k>N这就是说不属于L，这与泵引理矛盾。所以，L不是RL。五、构造等价于下图所示DFA的正则表达式。(12分)Sq1q0q2q310001110答案(之一)：(01+(1+00)((1+00*1)0)*((1+00*1)1))*(e+(1+00)((1+00*1)0)*00*)q1q0q2q310001110eeXYe预处理：去掉q3：q1q0q21011+00*10eXYe00
31、*去掉q1：q0q21+00(1+00*1)0eXYe00*(1+00*1)101q0eXYe+(1+00)((1+00*1)0)*00*01+(1+00)((1+00*1)0)*((1+00*1)1)去掉q2：去掉q0：XY(01+(1+00)((1+00*1)0)*((1+00*1)1))*(e+(1+00)((1+00*1)0)*00*)六、设M=（{}，{0,1}，{0,1，B}，{δ}，,B,{}）,其中δ的定义如下：δ（，0）=（，0，R）δ（，1）=（，1，R）δ（，0）=（，0，R）δ（，B）=（，B，R）请根据此定义，给出M处理字符串00001
32、000,10000的过程中ID的变化。（10分）解：处理输入串00001000的过程中经历的ID变化序列如下：0000100000001000000010000000100000001000000001000000001000000010000000100000001000B处理输入串10000的过程中经历的ID变化序列如下：100001000001000010000100001000010000B七、根据给定的NFA，构造与之等价的DFA。（14分）NFAM的状态转移函数如下表状态说明状态输入字符012开始状态q0{q0,q1}{q0,q2}{q0,q2}q1
33、{q3,q0}{q2}q
