2012-2013 答案1

《计算理论》是计算机科学中的核心课程之一，主要探讨计算问题的本质、算法的界限以及可计算性理论。2012-2013学年浙江大学的这门课程期末考试试卷涉及了多个计算理论的关键概念，包括正则语言、上下文无关语言、递归可枚举语言以及递归语言等。 1. 正则语言和正则表达式： - (a) 题目指出，{xyz | x, y, z ∈ {a, b}∗ and x = zR and |x| ≥ 1}是正则语言，因为这个集合可以通过一个右线性文法描述，即由x到y再到z的反向串，且长度至少为1，所以它是正则的。 - (b) 给定两个正则语言A和B，其对称差A⊕B=(A−B)∪(B−A)也是正则的，因为可以用DFA构造出接受A和B的并集，然后去除它们的交集，实现对称差。 2. 上下文无关语言和正则语言的关系： - (d) 语言{ambnckdl|m, n, k, l ∈ N, m ≥ l and n ≤ k}不是上下文无关的，因为它的产生需要记住多个不同位置的信息，而正则语言无法做到这一点。 - (e) 如果L1和L3都是上下文无关的，并且L1⊆L2⊆L3，那么L2也是上下文无关的，这是上下文无关语言的封闭性质。 3. 图灵机与可计算性： - (c) 每个确定型有限状态自动机（DFA）M都可以编码为字符串"M"，但语言{“M”| DFA M拒绝“M”}不是正则的，因为它涉及到DFA自我模拟，这不是正则语言能表达的。 - (g) 语言{“M” | Turing machine M在至少2013个输入上停机}是递归可枚举的，因为存在一种图灵机可以枚举所有停机的图灵机，但不是递归的，因为不能决定所有图灵机是否停机。 - (j) 语言{“M” | Turing machine M不在这条输入上停机}不是递归可枚举的，这是停机问题的变体，无法解决。 4. 递归可枚举语言和递归语言的性质： - (k) 递归可枚举语言在交集下封闭，但不在补集下封闭。这意味着我们可以枚举所有停机的图灵机，但无法确定所有不包含在枚举集合中的语言。 - (i) 存在一个语言L，既是递归可枚举的，也是递归的。例如，空语言和全集都是这样的例子。 - (l) 由于可计算语言的数量是可数的，而可能的语言数量是不可数的，因此大多数语言不是递归可枚举的。 5. 非正则语言的证明方法： - (a) 证明L1={ambnck | m, n, k ∈ N and m ≠ n + k}不是正则的，通常可以使用泵引理。对于任何正则语言，如果其具有足够长的词，都可以被分解成三部分满足泵引理的条件，而在L1中，这个分解会导致矛盾，因此L1不是正则的。 - (b) 类似地，L2={ambnck | m, n, k ∈ N and (m ≡ (n + k)) mod 2}的证明也涉及到对正则语言限制的分析，这里需要展示对于任何试图接受L2的DFA，都存在一种输入使得DFA无法正确识别模2的加法关系。 这些题目涵盖了计算理论的基本概念，如正则语言的定义和性质，上下文无关语言与正则语言的关系，图灵机的可计算性和不可计算性，以及递归可枚举语言的特性。理解和掌握这些知识点对于深入学习计算机科学和进一步探索算法复杂度、计算模型等领域至关重要。