形式语言与自机理论试题.doc

形式语言与自动机理论试题 一、按要求完成下列填空 给出集合{Φ,{Φ}}和集合{ε,0,00}的幂集 （2x4） (1) {Φ,{Φ},{{Φ}},{Φ,{Φ}}} (2) {Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{ε,0,00}} 设∑={0,1},请给出∑上的下列语言的文法 （2x5） 所有包含子串01011的串 S→X01011Y X→ε|0X|1X Y→ε|0Y|1Y (2)所有既没有一对连续的0，也没有一对连续的1的串 A→ε|A’|A” A’ →0|01|01A’ A” →1|10|10A” 构造识别下列语言的DFA 2x6 (1) {x|x?{0，1}+且x以0开头以1结尾} （设置陷阱状态，当第一个字符为1时，进入陷阱状态） (2) {x|x?{0，1}+且x的第十个字符为1} （设置一个陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态） 二、判断（正确的写T，错误的写F） 5x2 1.设和是集合{a,b,c,d,e}上的二元关系，则 ( T ) 任取(x.,y),其中x,y，使得。 2.对于任一非空集合A，Φ ( T ) 3.文法G：S A|AS A a|b|c|d|e|f|g 是RG ( F ) 4.3型语言2型语言1型语言0型语言 ( T ) 5.s（rs+s）r=rrs（rrs） ( 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分）。 bB→bb CB→BC bC→bc cC→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 四、判断语言{|n=1}是否为RL，如果是，请构造出它的有穷描述(FA,RG或者RL）；如果不是，请证明你的结论（12分） 解：设L={|n=1}。假设L是RL，则它满足泵引理。不妨设N是泵引理所指的仅依赖于 L的正整数，取Z= 显然，Z∈L 。 按照泵引理所述，必存在u，v，w。由于|uv|=N,并且|v|=1，所以v只可能是由0组成的非空串。不妨设v=，k=1 此时有u= ，w= 从而有uvw= 当i=2时，有uvw= 又因为k=1, 所以 N+kN 这就是说不属于L， 这与泵引理矛盾。所以，L不是RL。 五、构造等价于下图所示DFA的正则表达式。(12分) Sq S q1 q0 q2 q3 1 0 0 0 1 1 1 0 答案(之一)：( 01+(1+00)((1+00*1)0)*((1+00*1)1) )* (?+(1+00)((1+00*1)0)*00*) q1 q1 q0 q2 q3 1 0 0 0 1 1 1 0 ? ? X Y ? 预处理： 去掉q3： q1 q1