形式语言与自动机试题及答案

时间：2022-11-23 08:35:00 期末试题我要投稿

相关推荐

形式语言与自动机试题及答案

　　形式语言与自动机这门课程比较深奥，内容复杂，要学好这门课程不容易，同学们要用心去学才能学好形式语言与自动机。下面是阳光网小编给大家整理的形式语言与自动机试题及答案，欢迎大家学习参考。

形式语言与自动机试题及答案

　　《形式语言与自动机》期末测试题 (规定时间:2 小时)

　　1. (12 pts) 选择填空(多选): (a) 由正规表达式 a* 定义的语言 ; A,C(或只回答 C) (b) 语言 {a m b m ?m ?0} ; B (c) 语言 {a m b m c m ?m ?0} ; D (d) 语言 {a m b n c m ?m,n ?0} ; B (e) 对角化(diagonalization)语言 L d ;F (f) 通用语言(universal)语言 L u ;E 供选择的答案: A. 是某个有限状态自动机的语言; B. 是某个下推自动机的语言, 但不是任何有限状态自动机的语言; C. 是某个有限状态自动机的语言,但不是任何空栈接受方式的确定下推自动机的语言; D. 是某个可停机的图灵机的语言, 但不是任何下推自动机的语言; E. 是某个图灵机的语言, 但不是任何可停机的图灵机的语言; F. 不是任何图灵机的语言. 2. (7 pts) 图灵机({ q 0 , q 1 , q 2 , q 3 }, { 0,1 }, { 0,1,B }, ?, q 0 , B, {q 3 })有如下转移规则: ?(q 0 , 0)=(q 1 ,1, R) ?(q 1 , 1)=(q 2 , 0, L) ?(q 2 , 1)=(q 0 , 1, R) ?(q 1 , B)=(q 3 , B, R) 给出从初始ID q 0 0110开始, 该图灵机可以到达的完整的ID序列, 直到它停机 . 3. (12 pts) 设有四个语言(或问题)A，B，C 和 D. 这些语言可以是，也可以不是递归可枚举语言，但已知如下条件: (此题出得不好) i. A 可以归约到 B(不一定是多项式时间归约，下同); ii. B 可以归约到 C; iii. D 可以归约到 C; 对于以下 6 个命题，分别指出它们是“真”，或是“假”，或是“不能确定”: (a) A 是递归可枚举的但不是递归的，而 C 是递归的`. 假(A 不是递归的与C是递归的不可能同时成立) (b) B 不是递归的，而 D 是递归可枚举的. 不能确定 (c) A 的补不是递归可枚举的，而 B 的补是递归可枚举的. 不能确定 (d) B 的补不是递归的，而 C 的补是递归的. 假 (e) 如果 A 是递归的，那么 B 的补是递归的. 不能确定 (f) 如果 C 是递归的，那么 D 的补是递归的. 真