资源描述：
《形式语言与自动机理论试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
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&
12、#39;(1){x
13、x?{0，1}+且x以0开头以1结尾}（设置陷阱状态，当第一个字符为1时，进入陷阱状态）(2){x
14、x?{0，1}+且x的第十个字符为1}（设置一个陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态）二、判断（正确的写T，错误的写F）5x2'1.设R1和R2是集合{a,b,c,d,e}上的二元关系，则(T)任取(x.,y),其中x,y?{a,b,c,d,e}，使得(x,y)?(R1?R2)R3。??z((x,z)?R1?R2?(z,y)?R3)z?{a,b,c,d,e}??z((x,z)?R1?(x,z)?R2?(z,y)?R3)??z(
15、(x,z)?R1?(z,y)?R3)??z((x,z)?R2?(z,y)?R3)?(x,y)?R1R3?(x,y)?R2R3?(x,y)?R1R3?R2R3(R?R)R?RR?RR12313232(T)2.对于任一非空集合A，Φ?3.文法G：A
16、ASa
17、b
18、c
19、d
20、e
21、f
22、g是RG(F)4.3型语言2型语言1型语言0型语言(T)A??5.s（rs+s）*r=rr*s（rr*s）*(F)不成立，假设r,s分别是表示语言R，S的正则表达式，例如当R={0}，S={1},L(s(rs+s)*r)是以1开头的字符串，而L(rr*s(rr*s)*)是以0开头的字符串.L(s(
23、rs+s)*r)?L(rr*s(rr*s)*)所以s(rs+s)*r?rr*s(rr*s)*,结论不成立三、设文法G的产生式集如下，试给出句子aaabbbccc的至少两个不同的推导（12分）。S?aBC
24、aSBCaB?abbB→bbCB→BCbC→bccC→cc推导一：S=>aSBC=>aaSBCBC=>aaaBCBCBC=>aaabCBCBC=>aaabBCCBC=>aaabbCCBC=>aaabbCBCC?=>aaabbBCCC=>aaabbbCCC=>aaabbbcCC=>aaabbbccC=&
25、gt;aaabbbccc推导二：S=>aSBC=>aaSBCBC=>aaaBCBCBC=>aaaBBCCBC=>aaaBBCBCC=>aaabBCBCC=>aaabbCBCC=>aaabbBCCC=>aaabbbCCC=>aaabbbcCC=>aaabbbccC=>aaabbbccc四、判断语言{0n1n0n
26、n>=1}是否为RL，如果是，请构造出它的有穷描述(FA,RG或者RL）；如果不是，请证明你的结论（12分）解：设L={0n1n0n
27、n>=1}。假设L是RL，则它满足泵引理。
28、不妨设N是泵引理所指的仅依赖于L的正整数，取Z=010显然，Z∈L。按照泵引理所述，必存在u，v，w。由于
29、uv
30、<=N,并且
31、v
32、>=1，所以v只可能是由0组成的非空串。不妨设v=0，k>=1此时有u=0uvw=0iNNNkN?k?j，w=010从而有jNNN?k?j(0k)i0j1N0N当i=2时，有uv2w=0N?k1N0N又因为k>=1,N?kN所以N+k>N这就是说010N不属于L，这与泵引理矛盾。所以，L不是RL。五、构造等价于下图所示DFA的正则表达式。(12分)0?+(1+00)((1+00*1)0)*00*)3去掉q3
33、：去掉q1：3YYY去掉q2：去掉q0：Y01+(1+00)((1+00*1)0)*((1+00*1)1)(01+(1+00)((1+00*1)0)*((1+00*1)1))*(?+(1+00)((1+00*1)0)*00*)Y六、设M=（{q0,q1,q2}，{0,1}，{0,1，B}，{δ}，q0,B,{2}）,其中δ的定义如下：δ（0，0）=（q0，0，R）δ（q0，1）=（q1，1，R）δ（q1，0）=（q1，0，R）δ（1，B）=（q2，B，R）请根据此定义，给出M处理字符串00001000,10000的过程中ID的变化。（10分）解：处理输入串000
