计算理论期末复习：从有穷自动机到图灵机的核心知识点速查

简介面向哈工程等高校计算机专业学生的计算理论期末考点梳理专治“背不下来”的焦虑。内容按自动机理论、图灵机、语言理论、计算复杂度理论等模块展开系统汇总正则语言封闭性、DFA/NFA 等价、图灵机格局、可判定/可识别语言、映射可归约、P 与 NP 等核心知识并列出 A_DFA、A_NFA、A_REX、EDFA、EQDFA、A_CFG、A_LBA 等可判定语言以及 A_TM、停机问题、ETM、REGULAR_TM、EQTM、PCP 等不可判定语言便于对照记忆。文档采用条目化速记风格对“图灵可识别”与“图灵可判定”、“判定器”与“识别器”、“可计算函数”与“归约”等易混淆概念做了清晰对比尤其适合考前集中背诵与查漏补缺。资源包仅含一个 docx 文件大小仅 18KB内容以条目式索引组织轻量易读便于打印或导入平板标注方便快速查阅。已有 549 人浏览学习是期末突击计算理论的实用笔记。1. 计算理论期末复习这份知识点清单到底在讲什么计算理论期末复习最头疼的不是做题是背——有穷自动机、上下文无关文法、图灵机、可判定性、不可判定性、P与NP几十个概念互相嵌套错一个就连锁崩盘。这份《计算理论知识点》把多数高校期末卷的考点浓缩成一条条可以直接引用的结论从「有穷自动机识别的是正则语言」到「萨维奇定理」再到「L ⊆ NL ⊆ coNL ⊆ P ⊆ NP ⊆ PSPACE ⊆ NPSPACE」这条复杂度包含链全部按命题形式列好说穿了就是“背下来你就好了”。它不铺开解释定理的证明过程只负责把“是什么、考什么、怎么推”讲明白。适合期末冲刺阶段拿来逐条过知识点也适合刷题时当速查卡用。如果前面复习得稀碎这份清单能帮你把知识框架重新钉住。2. 从有穷自动机到正则语言三张等价身份证与封闭性证明2.1 正则语言的三张等价身份证文档第1条、第4条、第6条、第7条放在一起看其实就一句话正则语言有三种等价描述方式——DFA、NFA、正则表达式。第1条说“被有穷自动机识别的是正则语言”这是定义的入口第4条用“当且仅当”补上反方向即一个语言是正则的当且仅当有一台非确定型有穷自动机识别它第6、7条引入正则表达式说“一个语言是正则的当且仅当有一个正则表达式描述它”“如果一个语言是正则的则可以用正则表达式描述它”。注意第6条是充要条件第7条是单向条件考试常拿这种细节做陷阱。这三张身份证意味着期末题有大量“换表示”的考法给你正则表达式让你画NFA给你DFA让你写出等价的正则表达式或者给你一个状态图让你判断它识别的语言是不是正则语言。第3条“每一台非确定有穷自动机都等价于一台确定型有穷自动机”是三种表示能自由切换的底层依据。NFA看起来比DFA多了一个“同时处于多个状态”的能力但这个能力并没有扩大语言类子集构造法可以把任何NFA转成等价的DFA。理解了这个构造就能回答“NFA和DFA谁更强”这种送分题——两者等价谁也不比谁强。第5条是经常被忽略的小点空集连接到任何集合上得到空集空串连接到任何一个串上不改变这个字符串。注意空集是语言层面的“一个元素都没有”空串是串层面的“长度为0”。所以空集连接任何语言结果还是空集空串连接任何串结果还是那个串。这两个符号长得像含义完全不同填空题最容易在这里翻车。2.2 封闭性证明的构造思路第2条说正则语言在并运算、连结、星号运算下封闭。别小看这条期末证明题里它几乎必考但很多人写不好构造。核心思路是用NFA而不是DFA做构造因为NFA允许空串转移拼装机器非常方便。并运算的构造给两台NFA分别加一个全新的起始状态从这个状态引两条空串边分别指向两台机器原来的起始状态接受状态保持两台机器原有的接受状态不变。这样输入串只要被任意一台机器接受整体就接受。连结的构造把第一台NFA的所有接受状态都加上空串边指向第二台NFA的起始状态然后把第一台的接受状态从接受状态集合里去掉第二台的接受状态作为整体的接受状态。这样输入串必须先完整走完第一台再进入第二台。星号运算的构造在原来的NFA上新增一个起始状态兼接受状态再从新增状态和原有接受状态各加空串边回到原起始状态形成“跑完一轮还能再跑一轮”的通路。这样零次、一次、多次都能接受。这三个构造建议亲手在纸上各画一遍。考试时即使忘了细节也能根据“闭包”这个直觉现场推出来。封闭性说明一个问题并、连结、星号这三个运算不会把正则语言带到正则语言之外这个结论在后面可判定性题目里会反复用到。补一个容易混淆的点正则语言在交运算和补运算下也封闭但这份文档没有列原因是交和补需要用积构造证明和并运算的构造不是一套思路。期末如果问“正则语言的交是否封闭”答案依然是封闭的但证明时不要和并的构造混在一起。2.3 NFA转DFA为什么“非确定”不增加能力这一节把子集构造法的步骤写细一点属于每次考前都值得重看一遍的内容。第一步初始化把NFA起始状态的“空串闭包”作为DFA的起始状态。空串闭包指从该状态出发仅靠空串转移能到达的所有状态集合。第二步逐步扩张对当前DFA状态它是NFA状态的一个集合S逐个读入输入符号a计算S中每个状态经过a能到达的状态再对这些状态取空串闭包得到一个新的状态集合把它作为DFA的转移目标。如果这个集合还没出现过就加入DFA的状态集合。第三步标记接受状态凡是集合里包含NFA接受状态的DFA状态都标记为DFA的接受状态。重复第二步直到没有新状态产生算法结束。最坏情况新状态数达到2的n次方n是NFA状态数所以考试题里状态数一般控制在4个以内不会让你写出几十个状态的转移表。理解为什么要做空串闭包空串转移不消耗输入符号它只是“并行搬家”所以每读一个符号要把所有靠空串能到达的位置一并装进当前集合。这一步漏掉构造出的DFA就会丢串。常见做法是在草稿纸上先画出完整的空串闭包表再逐符号填转移虽然慢一点但不容易漏。3. 上下文无关语言与下推自动机乔姆斯基范式和栈式记忆的等价逻辑3.1 PDA与CFG的双向等价第9条和第10条是一对完整命题一个语言是上下文无关的当且仅当存在一台下推自动机识别它。第10条是正向第9条是反向。下推自动机可以理解为DFA加一个栈栈能存无限多的符号但只能从栈顶读写。这个“栈”给了PDA递归记忆能力使它恰好能处理那些需要“数数”的语言比如0的n次方1的n次方这种前后数量对应的串。为什么CFG和PDA等价直觉是文法推导从起始变量开始每一步把变量替换成产生式右侧的串PDA则可以用栈模拟这个过程——把起始变量压栈每读一个终结符和栈顶对一下并弹出每遇到栈顶是变量就选择一条产生式把变量弹出再把产生式右侧逆序压栈。反过来从PDA也可以构造等价CFG思路是把“从状态p到状态q栈深变化正好抵消”编码成一个变量。期末一般只考简单例子比如给定一个很短的文法让你构造PDA或者在选择题里判断“上下文无关当且仅当PDA识别”这种等价性。注意PDA有两种接受方式按接受状态接受和按空栈接受。两种定义下PDA的能力是等价的但转换算法不一样。试卷上如果画了PDA却没标注接受方式要先看它有没有画接受状态再决定怎么分析。这个细节容易被忽略实际考试中出现过不少次。3.2 乔姆斯基范式把CFG换成标准形态第8条任何一个上下文无关语言都可以用乔姆斯基范式的上下文无关文法产生。CNF的规则限制得很严要么A→BC两个非终结符要么A→a一个终结符加上可选的S→ε。期末最常见的题型是给你一个普通CFG让你转成CNF。转换有四个标准步骤每步都有自己的坑。第一步消去空串产生式。找出所有能推导出空串的变量然后为每个含该变量的产生式生成“去掉该变量”的版本。比如A→BC如果B能推导出空串则新增A→C如果B和C都能则A→B、A→C、A→空串也要考虑但最终A→空串通常要删掉除非A是起始变量。这里最容易漏掉的是新增多个组合版本。第二步消去单元产生式。单元产生式是A→B这种右侧只有单个变量的规则。对每个A→B把B的所有产生式复制一份给A然后删掉A→B。注意复制时如果B还有其他单元产生式要先处理传递闭包否则删不干净。第三步拆长产生式。A→B1B2…Bkk大于等于3时引入新变量把长产生式拆成两两一组。第四步处理无用符号。把不可达的变量和推导不出终结符串的变量删掉。这步容易被忽略但标准答案里通常要求写清楚。CNF为什么重要因为有了规范形态判断“给定CFG是否接受某个串”就有了固定算法CYK算法一个按子串长度从小到大填表的动态规划。期末考试如果考“判定ACFG”原理就是先转成CNF再跑CYK。虽然手算不会真跑完整张表但知道这一层会让你做概念题时不容易懵。3.3 正则 ⊂ 上下文无关 ⊂ 可判定第11条“每一个正则语言都是上下文无关的”是一条包含关系。为什么成立因为DFA本身就可以看成一台从来不用栈的PDA——它不用栈也能处理正则语言所以正则语言全部落在上下文无关语言这个更大的集合里。反过来上下文无关语言里有大量不是正则的例子最经典的就是0的n次方1的n次方DFA数不清前一半的0和后一半的1是否数量相等但PDA可以用栈压一个0弹一个1轻松搞定。文档第12条里还有两个可判定结论ACFG上下文无关文法是否接受某个给定串是可判定的ECFG上下文无关文法是否为空也是可判定的。前者靠CYK算法后者靠检查起始变量是否能推导出终结符串。另外还有一句“每一个上下文无关语言是可判定的”意思是上下文无关语言本身是递归语言存在一台图灵机在有限步内判定任意串是否属于它。这条线把正则、上下文无关和图灵可判定串起来了正则语言 ⊆ 上下文无关语言 ⊆ 可判定语言。这个包含链条看着简单但它揭示了后面复杂度章节的一条暗线三个语言类从简单到复杂判定难度递增可判定性却都还是“良性的”。真正出问题的是图灵机那种带循环的识别过程。4. 图灵机的三种结局可识别、可判定与永不停机4.1 格局与计算历史图灵机运行的快照文档第1条讲格局当前状态、当前带内容和读写头当前的位置这三样组合在一起就是图灵机的一个格局。一句话理解就是“某一瞬间机器的完整状态快照”。计算历史是格局序列C1到Cl其中C1是起始格局Cl是接受格局或拒绝格局且每个Ci都是Ci-1经一步转移得到的结果。计算历史都是有限序列如果机器永不停机就既没有接受历史也没有拒绝历史。计算历史的性质非常关键确定型图灵机在给定输入上最多只有一个计算历史因为每一步转移都是唯一确定的非确定型图灵机在单个输入上可能有多个计算历史对应多个分支。这些性质在后面证明不可判定性时会被反复用到——尤其是“计算历史法”把“是否存在一个符合规则的合法序列”编码成某个判定性问题再归约到已知不可判定的问题上。考试里关于格局最常出的题是给一个图灵机运行的中间快照让你写出下一个格局或者判断当前格局是否能被接受。只要记住格局三要素——状态、带上内容、读写头位置——迁移一步就够。注意读写头位置通常用带符号序列中当前字符上方加标记表示别漏掉带两端可能的空白符号。4.2 三种结局与判定器的边界文档第4条在输入上运行一个图灵机可能出现接受、拒绝、循环三种结果。循环就是不停机但它不一定是以同样的方式重复同样的步骤——这是初学者最容易理解错的地方。“循环”不代表机器在绕圈而是代表它永远不停止可能每次都在做不一样的事。图灵机有两种不接受输入的方式一种进入拒绝状态然后停下来另一种是进入循环也算不接受。这两种不接受在可识别性的定义里地位截然不同。判定器是“在所有输入上都停机”的图灵机。它永远不循环总能决定接受还是拒绝。所以可判定语言的条件比可识别语言强得多图灵可识别只要求“语言里的串一定能被接受”非本语言的串可以不停机图灵可判定要求所有串都给出明确答复。第5条“每一个可判定语言都是图灵可识别的”是显然的但反过来不成立。第14条给了精确的等价条件一个语言是可判定的当且仅当它既是图灵可识别的也是补图灵可识别的。这条定理在期末题里出现频率极高经常以“L可识别L的补也可识别问L是否可判定”的形式出现。答案是可判定因为两个识别器可以交替运行谁先接受就输出谁的结果。这个构造思路也解释了为什么“补图灵可识别”这个概念会被单独定义出来。4.3 多带、非确定与丘奇-图灵论题文档第6条、第7条是两条等价性结论每条多带图灵机都等价于一台单带图灵机每台非确定型图灵机都等价于一台确定型图灵机。这两条合起来的含义是图灵机的能力不因为“多几条带子”或“多一个不确定选择”而变强。非确定型图灵机“猜”一个答案的能力在可计算性层面没有扩大图灵可识别语言类。第8条、第9条又把这种等价性写成语言类层面的充要条件一个语言是图灵可识别的可判定的当且仅当存在非确定型图灵机识别判定它。但这里要特别强调等价是“可计算性层面”的等价不是“效率层面”的等价。多带转单带会引入平方级时间开销非确定转确定是指数级开销。很多同学在P与NP问题上懵根源就是把这两个层面的等价混在了一起。可计算性等价只能说“能不能算”复杂度等价才是“算得快不快”两者不是一回事。第10条丘奇-图灵论题也很好考算法的直觉概念就等同于图灵机可计算。它是一条论题而不是定理没有办法被证明但所有已知计算模型都满足这个边界。第11条三种描述层次是另一种考法形式化描述要把状态和转移函数全部写出来最详细也最啰嗦实现描述用日常语言讲机器怎么管理带子和读写头不需要列转移函数高水平描述直接用算法语言描述完全不提图灵机的带子和读写头。考试要你判断“某个描述属于哪一层”的时候就看它有没有出现状态集合、转移函数、读写头这一类术语。出现完整状态和转移函数的是形式化描述只提带子和读写头但不提状态的是实现描述全程不提机器细节的是高水平描述。第17条线性有界自动机是受限图灵机读写头不能离开包含输入带的区域试图越界时读写头原地不动。线性有界自动机的格局数量是输入长度的指数级所以ALBA是可判定的但ELBA是不可判定的这个反差值得记一下后面章节会用到。提示复习这一章时把“可识别”“可判定”“停机”三个词在每道题里圈出来这三个词的差异就是这一章大部分考点的分水岭。5. 可判定性判断避坑指南不可判定清单与归约方向的血泪经验5.1 可判定清单哪些问题能算出答案文档第12条先给出了一个可判定名单ADFADFA是否接受给定串、ANFANFA是否接受给定串、AREX正则表达式是否生成给定串、EDFADFA是否接受空语言、EQDFA两台DFA是否接受同一语言、ACFGCFG是否生成给定串、ECFGCFG是否生成任何串、ALBALBA是否接受给定串。这些判定问题为什么可判定每个的算法各不相同。ADFA直接模拟DFA跑一遍输入跑到头看是否停在接受状态ANFA和AREX先转成DFA再模拟EDFA做一个从起始状态出发的图搜索看能不能到达接受状态EQDFA的思路更巧妙——构造一台“对称差自动机”它接受正好被其中一台接受、不被另一台接受的串然后判空ACFG用CYK算法ECFG检查起始变量能否推导出终结符串ALBA因为线性有界自动机的格局数是有限的可以在所有有限格局的范围内做搜索。把这份名单记牢做题时先把名字对号入座再谈其他。5.2 不可判定清单哪些问题根本算不出另一份名单更让考生头大。不可判定的问题包括ATM给定图灵机M和串wM是否接受w、停机问题HALTTMM在w上是否停机、ETMM是否不接受任何串、REGULARTMM识别的语言是否正则、EQTM两台图灵机是否接受相同的串、ELBA线性有界自动机是否不接受任何串、ALLCFGCFG是否生成所有串、PCP波斯特对应问题。文档里写的“波斯地图对应实例”是PCP的翻译差异按“波斯特对应问题”记就好。这里要分清不可判定的证明路径。ATM本身用对角化法证明假设存在判定器H构造一台“反着来”的机器DD问H“D自己是否接受w”然后给出相反答案导致逻辑矛盾。其他问题大多靠归约证明——把ATM归约到目标问题如果目标问题可判定ATM就可判定矛盾。所以复习策略很清晰先把ATM不可判定这个根记牢再把每条归约的大方向记清楚细节题靠现推。文档第12条还给了两个更进阶的结论ATM的补是不可识别的不光是不可判定连可识别都做不到EQTM既不是图灵可识别的也不是补图灵可识别的。复习到后期要能区分“不可判定但可识别”如ATM本身和“连识别都不可”如ATM的补和EQTM两类问题。这两类在选择题里经常以“下列说法正确的是”的形式出现。5.3 映射可归约方向决定一切第18条到第22条是映射可归约的定义和性质。一句话存在一个可计算函数f把问题A的每个实例w映射成问题B的实例f(w)并且w属于A当且仅当f(w)属于B。记作A ≤m Bf就叫从A到B的归约。第20条定义了可计算函数本身存在图灵机在任意输入w上停机时带上恰好留下f(w)。第21条把这个定义用到语言上就是语言A映射可归约到语言B的完整条件。由这个定义得到两个最常用的推论也是第22条的内容如果A ≤m B且A不可判定则B不可判定如果A ≤m B且B图灵可识别则A图灵可识别。方向特别容易被记反。想做“证明B不可判定”的题目正确姿势是找出一个已知不可判定的A比如ATM构造f把A归约到B然后由第一条推出B不可判定。如果你写的是B ≤m A那是归约方向搞反了结论推不出来。证明REGULARTM不可判定的经典思路就是构造函数f输入是(M,w)输出一台新机器M。M先模拟M在w上的运行如果M接受wM就只接受一个固定的非正则语言比如0的n次方1的n次方如果M不接受wM不接受任何串。于是“M是否接受w”被编码成了“M识别的语言是否正则”的反面严格说是把ATM归约到REGULARTM的补再由补可判定推出原问题可判定会产生矛盾从而证明REGULARTM不可判定。理解了这条思路类似ETM、EQTM的证明都能顺下来。5.4 避坑常见问题期末高频混淆点记录坑一把“图灵可识别”当成“图灵可判定”。 现象题目说“一个语言能被某图灵机识别”选项直接判它“是可判定的”。 原因初学者只记了“识别”这个词里有“可”字没注意到识别器允许在拒绝方向陷入循环。 解决做题先划关键词——题里写的是“识别”还是“判定”。识别是存在性只要语言里的串能被接受就行判定是全称性所有输入都必须停机给出结果。没有“判定器”或“停机”相关表述就不能推可判定。坑二补图灵可识别验证时漏了方向。 现象证“L可判定”只说明L可识别就收工。 原因可判定当且仅当可识别且补可识别两个条件都要满足。 解决按模板写两句话“L可识别理由…L的补可识别理由…由定理L可判定。”如果其中一个方向给不出来题目大概率是想考不可判定。坑三归约方向写反。 现象要证B不可判定写“B ≤m A”还觉得没毛病。 原因把“用B的解法解决A”误记成“用A解决B”。 解决每次写归约前先默念“从已知到未知”左手是已知不可判定的A右手是待证的Bf把A的实例翻译成B的实例。写完后检查一遍翻译后的实例是否属于B跟原实例是否属于A保持一致。坑四空集和空串的运算混用。 现象填空题“空集和任意语言L连接结果是”填了L甚至填了空串。 原因空集与空串形近义不同。 解决把空集看成“一个元素都没有的集合”它连接任何集合都没有元素可选结果只能是空集空串是“一个长度为0的串”它连接任何串也只是原串。坑五3SAT归约到CLIQUE的方向记反。 现象默写“3SAT ≤p CLIQUE”时写成了“CLIQUE ≤p 3SAT”。 原因只记住两个都在NP完全清单里忽略了归约链的具体方向。 解决用库克-列文定理锁定SAT是NP完全再用“子句到团”的编码记住3SAT归约到CLIQUE。考试现场推不出来时就用定义验证CLIQUE要求“是否存在k个两两相邻的顶点”这个结构偏图论不容易被编码成布尔公式而3SAT的子句天然可以编码成图所以方向是从3SAT到CLIQUE。6. 复杂度类怎么读才不糊从P到PSPACE的自测验证法6.1 复杂度定义与两条时间换算第24条定义时间复杂性类TIME(t(n))由时间O(t(n))的图灵机可判定的所有语言的集合。这里隐含了一个前提讨论复杂度时用的图灵机必须是判定器因为只有停机才有时间可言。第25条说每条多带图灵机都等价于某个O(t²(n))时间的单带图灵机第26条说每个t(n)时间的非确定型单带图灵机都等价于某个2^O(t(n))时间的确定型单带图灵机。这两条是多带转单带、非确定转确定在复杂度层面的“代价表”前者是平方级后者是指数级两者差距巨大。第36条定义了空间复杂性类SPACE(f(n))和NSPACE(f(n))第37条萨维奇定理把非确定空间压缩到确定空间的平方使得NPSPACE等于PSPACE。第40条对数空间转换器是归约的一种细化它要求归约函数本身在对数空间内可计算这是L与NL类内部讨论归约时默认使用的归约基准。6.2 归约关系与三个“完全”定盘星第28条和第30条是P与NP的具体成员PATH、RELPRIME、每个上下文无关语言都在P里HAMPATH、CLIQUE、SUBSET-SUM、SAT、3SAT、UHAMPATH都在NP里。第31条给了一个直觉对照P是成员可以快速判定的语言类NP是成员可以快速验证的语言类。第34条库克-列文定理SAT属于P当且仅当PNP这句话把SAT推成NP完全问题的原点。第35条给出3SAT多项式时间可归约到CLIQUE。PSPACE完全的代表是TQBF、FORMULA-GAME、GGNL完全的代表是PATH。6.3 自测验证法我期末前三天怎么用这份文档分享一个我自己的复习习惯。拿到这份知识点文档后我第一件事不是背而是把所有“当且仅当”语句单独抄出来做成双向卡片一边写条件一边写结论。比如“一个语言是可判定的当且仅当它既是图灵可识别的也是补图灵可识别的”盖住后半句默写前半句再反过来盖住前半句默写后半句。双向推得动才算真正记住单向能背不算数。第二件事是把不可判定清单按证明方法分组从ATM直接对角化的归一组经归约证明的归一组连识别都不行的归一组ATM的补、EQTM。分组之后考场上遇到没见过的判定问题先想它能不能用列表法做有穷搜索能则可判定再想ATM能不能归约到它能则不可判定。第三件事是考前最后一天把复杂度包含链默写三遍每写一遍都顺带写出每个类的一个代表语言。这套流程看着简单但我每次都是靠它把“好像背过但又说不太清楚”的知识点钉死。从那以后我期末复习计算理论都强制自己先过一遍这份文档再过一遍自测单再进考场。希望帮到你。本文还有配套的精品资源点击获取