形式语言与自动机课件形式语言与自动机2006年试卷未删节版.doc

《形式语言与自动机课件形式语言与自动机2006年试卷未删节版.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、《形式语言与自动机》考试试题2007．1．291.设Σ={a，b}上的有穷自动机M如下图所示：(35分)（1）先求T(M)；（2）再将M确定化为M’；（3）最后将M’极小化为M’’。2.回答下列问题，对不满足封闭性的运算给出其反例：(15分)1)rl类关于运算È（并），Ç（交），~（求补），×（连接），R（逆）和*（闭包）是否封闭？2)cfl类关于运算È（并），Ç（交），~（求补），×（连接），R（逆）和*（闭包）是否封闭？3.设Σ={a，b},试构造一个接受语言L1={w

2、w∈Σ*且#(w,a)=#(w,b)}的下推自动机M1，其中下推栈的栈底符号为Z0。(8分)4.给定字母表Σ={0，1}

3、，L2={w

4、w∈Σ*是非前0的符号串且

5、w

6、2可被5整除},其中

7、w

8、2是把w看成为非前0的二进制数。(8分)（1）构造一个接受L2的有穷自动机M2；或者（2）构造一个产生L2的正规文法G2；注：(1)或（2）任选一题。5.已知语言L3={anbmcn

9、n,m≥1},L4={anbm

10、1£n£m<2n}(30分)(1)构造产生L3的cfgG3；(2)构造产生L4的cfgG4；(3)证明语言L4不是正规语言。1.设Σ={a，b}，试构造一个产生语言L5={w

11、w∈Σ*且"uÎΣ*(w¹uu)}的cfgG5。(4分)