发老师-东华大学研究生考试试卷格式(A4)答案.docx

【知识点详解】 1. **确定性有限自动机 (DFA)**与**非确定性有限自动机 (NFA)** - DFA 和 NFA 都是形式语言理论中的模型，用于描述语言的接受过程。 - 区别在于 DFA 对每个输入只有一种计算路径，而 NFA 可能有多种路径，即可能存在多个接受状态的路径。 - 一个 NFA 能识别的语言 DFA 一定也能识别，但反过来不成立。因此，NFA 的识别能力更强。 2. **泵引理** - 泵引理是证明某些语言不是正则语言的重要工具。 - 基本思想是，如果一个语言是正则的，那么存在一个泵长 p，对于所有长度大于 p 的字符串，都可以通过“抽动”一部分来生成新的字符串，同时保持在语言内。若无法做到，则该语言不是正则的。 3. **下推自动机 (PDA)**与**图灵机 (TM)** - PDA 拥有一个有限状态控制和一个可以下推的栈，识别上下文相关语言，其识别能力弱于图灵机。 - 图灵机有无限存储带，可以识别所有可计算语言，包括上下文相关的和更复杂的语言。 4. **图灵可判定性 (Turing-decidable)** - 图灵可判定的语言是指存在一个图灵机，对于任意输入，都能确定该输入是否属于该语言，要么接受要么拒绝，不会无限循环。 - 若一个语言不是图灵可判定的，意味着不存在这样的图灵机。 5. **集合的可数性** - 一个集合如果可以通过一对一的方式与自然数集合建立对应关系，那么它是可数的，否则是不可数。 - 实数集合是一个典型的不可数集合，因为它的大小超过了自然数集合。 6. **计算复杂性理论** - **P** 类是可以在多项式时间内解决的问题集合。 - **NP** 类包含在多项式时间内验证解的问题，但不保证能在多项式时间内找到解。 - **NP-complete** 是最难的 NP 问题，如果一个问题在 NP 中且可以归约到 NP-complete 问题，那么它也是 NP-complete。 - **NP-hard** 是至少与 NP-complete 同等难度的问题，即使它们不一定是 NP 的问题。 - **P=NP** 的问题是指是否存在一个问题，其解可以在多项式时间内验证也能在多项式时间内找到。 - **PSPACE** 是能在多项式空间内解决的问题集合。 7. **语言的分类** - **Turing-recognizable** 语言是可以被图灵机识别，但不一定能决定的。 - **EXPTIME** 是指能在指数时间复杂度内解决的问题集合。 - **PSPACE-hard** 问题是至少与 PSPACE 同等难度的问题。 8. **综合应用题** - 第一题涉及状态图与自动机的表示，要求将状态图转换为 5 元组的形式。 - 第二题利用泵引理证明某些语言不是上下文无关的。 - 第三题证明实数集合的不可数性，通常采用 Cantor 的对角线法。 - 第四题涉及 3CNF 公式的规约，转化为图论中的 VERTEX-COVER 问题。 - 第五题将 3CNF 公式规约为 SUBSET-SUM 问题的实例。 这些知识点涵盖了计算理论和理论计算机科学的基础内容，包括自动机理论、图灵可判定性、计算复杂性理论以及语言的性质。理解和掌握这些概念对于深入学习计算机科学至关重要。