【免费】2013带答案1资源-CSDN文库

需积分: 0 10 浏览量 2022-08-03 12:05:28 上传评论收藏 215KB PDF 举报

资源详情

资源评论

资源推荐

清华大学本科生考试试题专用纸

考试课程《形式语言与自动机》 A 卷 2013 年 6 月 22 日

学号：姓名：班级：

（注：解答可以写在答题纸上，也可以写在试卷上；交卷时二者都需要交回。）

一. (16 分) 判别下列各命题的真假性，回答 true 或者 false: (每小题 2 分)

1．若 L

1

 L

2

是正规语言，则 L

1

和 L

2

一定都是正规语言。

2．若 L

1

和 L

2

都是正规语言，则 L

1

 L

2

一定是正规语言。

3．若 L

1

 L

2

不是正规语言，则 L

1

和 L

2

都不是正规语言。

4．判定一个串不能被某个有限自动机接受的算法是存在的。

5．存在一个判定任意两个正规表达式是否拥有相同语言的算法。

6．一个递归可枚举语言和它的补语言不可能都是递归语言。

7．非确定图灵机的语言所对应的问题是一个NP问题。

8．任何多带（multi-tape）图灵机均可由一个多道（multi-track）图灵机来模拟。

二. (12 分) 选择填空 (每小题 2 分)

1．语言 {0

n

21

m

 n  m } 。

2．语言 {0

n

21

m

 n  1, m  1，n + m  100} 。

3．语言 {0

n

1

m

2 n  1, m  1，n + m  100} 。

4．语言 { ww

R

 w  {0, 1}*，w

R

为 w 的反向 } 。

5．语言 { w2w w  {0, 1}* } 。

6．语言 { w2w

R

 w  {0, 1}*，w

R

为 w 的反向} 。

供 1、2 和 3 三小题选择的答案：

A. 是某个有限自动机的语言，也是某个空栈接受方式的 DPDA 的语言.

B. 是某个有限自动机的语言，但不是任何空栈接受方式的 DPDA 的语言。

False

True

False

True

True

False

False

True

E

C

A

B

D

F

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余5页未读，立即下载

评论0

内容反馈

文润观书

粉丝: 25
资源: 317

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip