1) 下图所示NFA接受的语言的补集是什么？假设 ∑ = {a}，ε 是空字符串
!NFA
(A) Φ
(B) ε
(C) a
(D) {a, ε}
答案 (B)
解析： 给定的字母表 ∑ 仅包含一个符号 {a}，且给定的NFA接受所有包含任意数量 ‘a‘ 的字符串。换句话说，该NFA接受 a+。因此，该自动机所接受语言的补集是空字符串。
2) 给定语言 L = {ab, aa, baa}，以下哪些字符串属于 L？*
1) abaabaaabaa
2) aaaabaaaa
3) baaaaabaaaab
4) baaaaabaa
(A) 1, 2 和 3
(B) 2, 3 和 4
(C) 1, 2 和 4
(D) 1, 3 和 4
答案 (C)
解析： 集合 {ab, aa, baa} 中字符串的任意组合都在 L* 中。
1) "abaabaaabaa" 可以被划分为集合 {ab, aa, baa} 中字符串的组合。划分为 "ab aa baa ab aa"。
2) "aaaabaaaa" 可以被划分为集合 {ab, aa, baa} 中字符串的组合。划分为 "aa aa baa aa"。
3) "baaaaabaaaab" 无法被划分为集合 {ab, aa, baa} 中字符串的组合。
4) "baaaaabaa" 可以被划分为集合 {ab, aa, baa} 中字符串的组合。划分为 "baa aa ab aa"。
3) 以下哪些问题是可判定的？
1) 给定的程序是否曾产生输出？
2) 如果 L 是上下文无关语言，那么 L‘（L 的补集）也是上下文无关语言吗？
3) 如果 L 是正规语言，那么 L‘ 也是正规语言吗？
4) 如果 L 是递归语言，那么 L‘ 也是递归语言吗？
(A) 1, 2, 3, 4
(B) 1, 2,
(C) 2, 3, 4
(D) 3, 4
答案 (D)
1) 这是图灵机停机问题的一个变体，它是不可判定的。
2) 上下文无关语言在交集和补集运算下是不封闭的。详情请参阅相关资料。
3) 正规语言的补集也是正规语言。接受 L 的补集（即 ∑* – L）的 DFA 可以通过将其接受状态与非接受状态互换来获得。
4) 递归语言在补集运算下是封闭的。详情请参阅相关资料。
4) 考虑 {0,1} 上的字符串集合，其中每个长度为 3 的子串中最多有两个 0。例如，001110 和 011001 在该语言中，但 100010 不在。所有长度小于 3 的字符串也在该语言中。一个接受该语言的未完成的 DFA 如下所示。
!DFA
DFA 中缺失的弧线是
答案 (D)
状态 ‘q’ 是陷阱状态。所有其他状态都是接受状态。在状态 00，对于输入符号 0，DFA 必须转移到 ‘q’。所有（非陷阱）状态的名称表示到达该特定状态之前看到的字符。选项 是唯一遵循这些规则的选项。
请参阅往年试卷、解答、解析、大纲、重要日期、笔记等所有相关内容。