计算理论导引第三版期中复习提纲

计算理论导引第三版期中复习提纲 计算理论是计算机科学的基础，涵盖了计算机科学的核心概念和技术。本文将从计算理论的六个方面进行总结，涵盖了正则语言、上下文无关语法、图灵机、可判定性、可归约性和反映递归定理等重要知识点。 第一章 正则语言 * 正则语言的封闭性证明：正则语言的封闭性是指对于任何正则语言L，对于任何字符串x，存在一个正则语言L'，使得L'包含所有以x为前缀的字符串。 * NFA 转化为等价的 DFA：非确定性有限自动机（NFA）可以转化为确定性有限自动机（DFA），这两个自动机都是计算理论中重要的模型。 * 有穷自动机转换成正则表达式：有穷自动机可以转换成正则表达式，从而可以用来描述语言的模式。 * 正则表达式转化成 NFA：正则表达式可以转换成 NFA，从而可以用来描述语言的模式。 第二章 上下文无关语法 * CFG 生成字符串的语法分析树和派生过程：.context-free grammar（CFG）可以用来生成字符串，并且可以通过语法分析树和派生过程来描述语言的结构。 * CFL 的不封闭性证明：context-free language（CFL）的不封闭性是指CFL不满足封闭性，无法将所有的CFL language转换成正则语言。 * 接受规定语言的 PDA 状态转移图或转移函数表：压入自动机（PDA）可以用来描述上下文无关语言的行为。 * 产生规定语言的 CFG：CFG可以用来产生规定语言。 * CFG 转化成等价的 PDA：CFG可以转换成PDA，从而可以用来描述语言的行为。 * CFG 转化成等价的 CNF：CFG可以转换成Chomsky Normal Form（CNF），从而可以用来描述语言的结构。 第三章 图灵机 * 图灵机的定义：图灵机是一个抽象的计算模型，可以用来描述计算机科学中的基本概念。 * 图灵机所计算的函数：图灵机可以计算各种函数，从简单的加法到复杂的计算。 * 图灵机的判定问题：图灵机可以用来解决判定问题，即确定一个字符串是否属于某个语言。 * 图灵机的可判定性：图灵机的可判定性是指图灵机可以解决判定问题的能力。 第四章 可判定性 * DFA 与正则表达式是否等价的问题表述为一个语言并证明其可判定性：DFA和正则表达式可以用来描述语言的模式，并且可以证明它们之间的等价性。 * ALLDFA 是可判定的：ALLDFA是指所有的DFA，它们都是可判定的。 * AεCFG 是可判定的：AεCFG是指所有的CFG，它们都是可判定的。 * 将给定语言进行分类（正则、上下文无关、图灵可判定、图灵可识别、补图灵可识别）：可以将语言分类为正则语言、上下文无关语言、图灵可判定语言、图灵可识别语言和补图灵可识别语言。 * 证明某个语言属于某个类别，而不能属于更小的类别：可以证明某个语言属于某个类别，而不能属于更小的类别。 第五章 可归约性 * 证明EQCFG是不可判定的：EQCFG是指所有的CFG，它们都是不可判定的。 * 证明EQCFG是补图灵可识别的：EQCFG是指所有的CFG，它们都是补图灵可识别的。 * 找出给定的 PCP 实例中的一个匹配：PCP是指Post Correspondence Problem，它是一个著名的计算理论问题。 * 映射可归约性A≤mB：可以证明A≤mB，从而可以用来描述计算理论中的可归约性。 第六章 反映递归定理 * 写一个将其自身打印出来的反映递归定理的例子：反映递归定理是一个重要的计算理论概念，可以用来描述计算机科学中的基本概念。 * 证明MIN TM的任何无限子集都不是图灵可识别的：MIN TM是指最小图灵机，它们的任何无限子集都不是图灵可识别的。 计算理论导引第三版期中复习提纲涵盖了计算理论的六个方面，包括正则语言、上下文无关语法、图灵机、可判定性、可归约性和反映递归定理等重要知识点。这将帮助读者更好地理解计算理论的基础知识和核心概念。