形式语言与自动机理论试题
一、按要求完成下列填空 
1.给出集合{Φ,{Φ}}和集合{ε,0,00}的幂集  （2x4）
        (1)  {Φ,{Φ},{{Φ}},{Φ,{Φ}}}
      (2)  {Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{ε,0,00}}
2.设∑={0,1},请给出∑上的下列语言的文法  （2x5）
wa字符串是什么(1)所有包含子串01011的串
          S→X01011Y
              X→ε|0X|1X
              Y→ε|0Y|1Y
      (2)所有既没有一对连续的0，也没有一对连续的1的串
            A→ε|A’|A”
                A’ →0|01|01A’
                A” →1|10|10A”
3.构造识别下列语言的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

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。