形式语言与自动机理论试题答案解析

形式语言与自动机理论试题答案解析一、按要求完成下列填空1.给出集合{Φ,{Φ}}和集合{ε,0,00}的幂集（2x4'）(1){Φ,{Φ},{{Φ}},{Φ,{Φ}}}(2){Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{ε,0,00}}2.设∑={0,1},请给出∑上的下列语言的文法（2x5'）(1)所有包含子串01011的串S→X01011YX→ε|0X|1XY→ε|0Y|1Y(2)所有既没有一对连续的0，也没有一对连续的1的串A→ε|A’|A”A’→0|01|01A’A”→1|10|10A”3.构造识别下列语言的DFA2x6'(1){x|x{0，1}+且x以0开头以1结尾}（设置陷阱状态，当第一个字符为1时，进入陷阱状态）1S01100,10(2){x|x{0，1}+且x的第十个字符为1}（设置一个陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态）1S0,10,10,10,10,110,0,10,10,10,10,1二、判断（正确的写T，错误的写F）5x2'1.设1R和2R是集合{a,b,c,d,e}上的二元关系，则3231321)(RRRRRRR(T)任取(x.,y),其中x,y},,,,{edcba，使得321)(),(RRRyx。)),(),((321RyzRRzxz},,,,{edcbaz)),(),(),((321RyzRzxRzxz)),(),(()),(),((3231RyzRzxzRyzRzxz3231),(),(RRyxRRyx3231),(RRRRyx2.对于任一非空集合A，ΦA2(T)3.文法G：SA|ASAa|b|c|d|e|f|g是RG(F)4.3型语言2型语言1型语言0型语言(F)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(rs+s)*r)L(rr*s(rr*s)*)所以s(rs+s)*rrr*s(rr*s)*,结论不成立三、设文法G的产生式集如下，试给出句子aaabbbccc的至少两个不同的推导（12分）。aSBCaBCS|abaBbB→bbCB→BCbC→bccC→cc推导一：S=aSBC=aaSBCBC=aaaBCBCBC=aaabCBCBC=aaabBCCBC=aaabbCCBC=aaabbCBCC=aaabbBCCC=aaabbbCCC=aaabbbcCC=aaabbbccC=aaabbbccc推导二：S=aSBC=aaSBCBC=aaaBCBCBC=aaaBBCCBC=aaaBBCBCC=aaabBCBCC=aaabbCBCC=aaabbBCCC=aaabbbCCC=aaabbbcCC=aaabbbccC=aaabbbccc四、判断语言{nnn010|n=1}是否为RL，如果是，请构造出它的有穷描述(FA,RG或者RL）；如果不是，请证明你的结论（12分）解：设L={nnn010|n=1}。假设L是RL，则它满足泵引理。不妨设N是泵引理所指的仅依赖于L的正整数，取Z=NNN010显然，Z∈L。按照泵引理所述，必存在u，v，w。由于|uv|=N,并且|v|=1，所以v只可能是由0组成的非空串。不妨设v=k0，k=1此时有u=jkN0，w=NNj010从而有uviw=NNjikjkN010)0(0当i=2时，有uv2w=NNkN010又因为k=1,所以N+kN这就是说NNkN010不属于L，这与泵引理矛盾。所以，L不是RL。五、构造等价于下图所示DFA的正则表达式。(12分)答案(之一)：(01+(1+00)((1+00*1)0)*((1+00*1)1))*(+(1+00)((1+00*1)0)*00*)预处理：去掉q3：去掉q1：q1q0q2q310001110XYq1q0q21011+00*10XY00*q0q21+00(1+00*1)0XY00*(1+00*1)101Sq1q0q2q310001110去掉q2：去掉q0：六、设M=（{210,,qqq}，{0,1}，{0,1，B}，{δ}，0q,B,{2q}）,其中δ的定义如下：δ（0q，0）=（0q，0，R）δ（0q，1）=（1q，1，R）δ（1q，0）=（1q，0，R）δ（1q，B）=（2q，B，R）请根据此定义，给出M处理字符串00001000,10000的过程中ID的变化。（10分）解：处理输入串00001000的过程中经历的ID变化序列如下：0q0000100000q0001000000q0010000000q0100000000q10000000011q00000000101q0000001001q0000010001q00001000B2q处理输入串10000的过程中经历的ID变化序列如下：0q1000011q00000101q0001001q0010001q0100001q10000B2q七、根据给定的NFA，构造与之等价的DFA。（14分）NFAM的状态转移函数如下表q0XY+(1+00)((1+00*1)0)*00*01+(1+00)((1+00*1)0)*((1+00*1)1)XY(01+(1+00)((1+00*1)0)*((1+00*1)1))*(+(1+00)((1+00*1)0)*00*)解答：状态说明状态输入字符012开始状态q0[q0,q1][q0,q2][q0,q2][q0,q1][q0,q1,q3][q0,q2][q0,q2][q0,q2][q0,q1][q0,q1,q2,q3][q0,q1,q2][q0,q1,q2][q0,q1,q3][q0,q1,q2,q3][q0,q1,q2]终止状态[q0,q1,q3][q0,q1,q2,q3][q0,q2,q3][q0,q2]终止状态[q0,q2,q3][q0,q1,q2,q3][q0,q1,q2,q3][q0,q1,q2]终止状态[q0,q1,q2,q3][q0,q1,q2,q3][q0,q1,q2,q3][q0,q1,q2]q0[q0,q1][q0,q2]01,22[q0,q1,q3][q0,q1,q2][q0,q2,q3][q0,q1,q2,q3]0,122001,20210,11状态说明状态输入字符012开始状态q0{q0,q1}{q0,q2}{q0,q2}q1{q3,q0}{q2}q2{q3,q1}{q2,q1}终止状态q3{q3,q2}{q3}{q0}