★ FEATURED ARTICLE 简介这份资料面向准备计算理论期末考核的计算机专业学生尤其适合哈工程等高校考生用作考前背诵与知识点梳理。内容围绕自动机理论、图灵机、语言理论与计算复杂度四大板块归纳了正则语言在有穷自动机下的识别条件、确定型与非确定型自动机的等价关系、格局与判定器的定义、图灵可识别与图灵可判定语言的区别以及映射可归约、P 与 NP、SAT 与 3SAT 等核心结论条目化呈现便于快速记忆。资源包内含 1 个 docx 文档约 18KB篇幅紧凑适合在手机上随时翻阅也方便打印成纸质速记卡。目前已有 553 人学习说明其在同类复习资料中具有一定认可度。读者可借此在考前集中串联定义、定理与典型不可判定问题配合课程笔记查漏补缺提高对判定性与复杂度概念的把握。1. 开考先看分值计算理论期末真正拉分的是“判定”不是“背诵”计算理论期末有个很常见的现象四十多条结论背得滚瓜烂熟的人照样在“A_TM 的补是不是图灵可识别的”这种题上卡住半分钟。这门课的分值分布其实很固定——选择、填空、判断考结论记忆三成左右证明题和判定题考你能不能把结论套到一个没见过的新语言上占七成。换句话说计算理论知识点不是拿来默写的是拿来当判定工具用的看到一个语言先定位它在哪一层正则 / 上下文无关 / 可判定 / 图灵可识别再问用什么机器识别它最后才问它落在哪个复杂度类里。背下来你就好了这句话只对前三成有效剩下的分要靠答题骨架。下面按这条主线拆先给能直接背的结论表再给真题的答法最后点出最容易翻车的几个地方。2. 正则语言三件套DFA、NFA、正则表达式的等价判定怎么答2.1 五个等价刻画与三条封闭性先背成一张表正则语言这门课给了五个说法考试喜欢在它们之间来回换词。能被确定型有穷自动机识别、能被非确定型有穷自动机识别、能被正则表达式描述、能被右线性正则文法产生、能被带 ε 转移的 NFA 识别这五句话说的是同一件事看到“一个语言是正则的当且仅当……”这种句式八成就是在考其中一个等价说法。判断题最常见的干扰项是把“有穷自动机”偷换成“下推自动机”或者把“当且仅当”改成“如果”读题慢一点就能避开。刻画方式判定或构造的抓手状态规模DFA直接给出转移表验证每个状态每个符号都有唯一后继n 个状态NFA允许同一符号多条出边、允许 ε 边通常比 DFA 少很多正则表达式Thompson 构造转 NFA状态消去法反向转回与运算符个数同阶右线性文法A → aB 或 A → a把变元当状态变元数即状态数封闭性分两档记。定义级的三条是并、连接、星号证明方式很套路给两台识别 L1、L2 的机器加一个新初态用 ε 边分叉或串联星号再加一条回到分叉点的 ε 边就完事。推论级的四条是补、交、反转、同态补最省事把 DFA 的接受状态和非接受状态对调即可交用乘积构造状态数是两台机器状态数相乘这条经常在选择题里被问成“交之后最多多少个状态”。两个关于空的小结论几乎每套卷子都出现而且专治记混空集连接到任何集合上得到空集这是语言层面的连接运算∅L ∅空串连接到任何一个串上不改变这个字符串这是串层面的连接εw w。把这两条写在一个括号里背考场上就不会把“空集”和“空串”对调。提示判断一个语言是否正则先问自己“要记住多少信息才能做完这道题”。有限个状态能装下的比如模 3 计数、是否以 011 结尾都是正则需要无限计数的0 和 1 是否一样多、0^n1^n就往泵引理上想。2.2 NFA 转 DFA子集构造的状态数到底怎么数“每一台非确定有穷自动机都等价于一台确定型有穷自动机”这条定理落到卷面上一般是一道构造题给一台 NFA要求画出等价的 DFA。手算的流程固定——DFA 的每个状态是 NFA 状态集的一个子集起始状态取初态的 ε 闭包对每个字母先求后继集合再取一次 ε 闭包出现新集合就加进队列直到不再产生新集合为止。理论上界是 2^n 个子集实际题目里能到的往往只有五六个但答题时要写清楚“至多 2^n”这是踩分点。手算容易漏状态尤其是 ε 边多的题。写过几行代码自查会稳很多下面的子集构造把 NFA 表示成字典跑一遍就能把状态表和接受状态一起打出来对着抄到卷面上不会错。# nfa: {状态: {符号: [后继状态]}}eps: {状态: [ε后继]} # start: 初态symbols: 字母表返回 {DFA状态(frozenset): {符号: 后继}} def subset_construct(nfa, eps, start, symbols): def closure(states): # 求 ε 闭包用栈避免递归过深 stack, out list(states), set(states) while stack: s stack.pop() for t in eps.get(s, []): if t not in out: out.add(t) stack.append(t) return frozenset(out) start_set closure({start}) dfa, queue, seen {}, [start_set], {start_set} while queue: cur queue.pop(0) # 取出一个未展开的子集 dfa[cur] {} for a in symbols: # 对每个字母求后继再取闭包 nxt set() for s in cur: nxt | set(nfa.get(s, {}).get(a, [])) nxt closure(nxt) dfa[cur][a] nxt if nxt not in seen: # 新子集才入队避免死循环 seen.add(nxt) queue.append(nxt) return dfaclosure负责把 ε 边一次走到底seen负责去重queue保证广度优先展开三层加起来就是标准子集构造。参数里最容易写错的是eps的结构考场手算时对应的动作是每求出一个后继集合都要再顺着 ε 边补一遍补完才算一个 DFA 状态。接受状态不用单独传展开结束后挑出“含原 NFA 接受状态”的那些子集即可这一步在卷面上要显式写一行说明。2.3 三道真题演练判断、构造、证明非正则第一题问 L {w ∈ {0,1}* | w 中 1 的个数是 3 的倍数} 是否正则若是请给出自动机。答题思路是先给结论“正则”再给构造三个状态 q0、q1、q2 分别表示当前 1 的个数模 3 的余数读 0 原地不动读 1 顺时针转一格q0 既是初态也是唯一的接受状态。踩分点在于说明“状态数有限且能覆盖所有前缀”只画图不解释会被扣过程分。第二题证明 L {0^n1^n | n ≥ 0} 不是正则语言。这是泵引理的入门题答法固定四步假设 L 正则设泵长度为 p取串 s 0^p1^p它长度不小于 p属于 L按泵引理写成 s xyz其中 |xy| ≤ p 且 |y| ≥ 1于是 y 只能是若干个 0把 y 重复两次得到 xy²z此时 0 的个数比 1 多不再属于 L矛盾。踩分点是必须点明“|xy| ≤ p 限制了 y 只能落在前半段”这一步不写后面重复两次的结论就悬空了。第三题证明 L {w | w 中 0 与 1 的个数相等} 不是正则。除了硬套泵引理还有一条更短的答法如果 L 正则那么 L 与 01的交也正则正则语言对交封闭而这个交恰好是 {0^n1^n}上一题已经证明它不是正则矛盾。这种“用封闭性把问题打回已知结论”的写法在考场上很吃香因为它同时展示了你记住了封闭性又省掉一次泵引理推导。第四题是封闭性的证明题证明正则语言对反转封闭。答法是把 DFA 的所有边方向反过来原来的接受状态全部改成初态必要时加一个新的唯一初态用 ε 边连到所有原接受状态原来的初态改成接受状态得到一台 NFA它识别的正好是原语言的反转。踩分点在于强调“反转之后得到的是 NFA 而不是 DFA”因为反向之后一个状态可能有多条同符号出边这个细节年年有人漏。3. 上下文无关语言乔姆斯基范式、PDA与CFL判定题的答法3.1 CFG、PDA、CNF三个名词其实是一条定理链上下文无关文法是一个四元组变元集合、终结符集合、产生式集合、起始变元。推导是从起始变元出发反复替换变元的过程最左推导是每步都替换最左边的变元语法分析树把同一个推导画成树形二义性指同一个串存在两棵不同的分析树。下推自动机比有穷自动机多一个栈状态转移时既能读输入也能压栈弹栈接受方式有终态接受和空栈接受两种两者可以互相转换。把这三个概念串起来的定理只有两条但考试反复考一个语言是上下文无关的当且仅当存在一台下推自动机识别它任何一个上下文无关语言都可以用乔姆斯基范式的上下文无关文法产生。乔姆斯基范式把产生式限制成两种形状A → BC 或者 A → a也就是右部要么恰好两个变元要么恰好一个终结符。转换步骤固定四步先消掉 ε 产生式起始变元允许保留 S → ε前提是空串属于语言再消掉单位产生式 A → B然后删掉产生不出终结符串的无用符号最后把右部长度超过 2 的产生式拆成一串二元产生式并处理混在变元里的终结符。封闭性这块要和正则语言对照着记不然特别容易串。上下文无关语言对并、连接、星号封闭证明方式是在文法层面加新起始变元拼产生式但它对交不封闭对补也不封闭反例的思路是拿两个上下文无关语言相交得到 {a^n b^n c^n} 这种非上下文无关的语言。这一对比几乎每年都以判断题或简答题的形式出现。提示看到“乔姆斯基范式”四个字先在草稿上写出 A → BC 与 A → a 两种形式再动笔转换。转换题的分数大多给在“消 ε、消单位”这两步的过程上只写结果拿不到多少分。3.2 A_CFG 与 E_CFG为什么它们可判定而 ALL_CFG 不可判定A_CFG 问的是一台文法 G 是否产生某个串 w这个问题可判定答法是先转乔姆斯基范式再用 CYK 算法做动态规划时间复杂度 O(n³)。CYK 的表格是一个上三角表项 (i, j) 放的是“能从第 i 个字符推到第 j 个字符的所有变元”长度从 1 开始往上填长度 1 直接查 A → a 型产生式长度大于 1 就枚举切分点 k把 (i, k) 和 (k1, j) 里的变元两两组合看能不能拼出某个 A → BC。答这道题时把表格画出来哪怕只填了一半过程分也基本稳了。E_CFG 问的是文法是否不产生任何串答法更简单标记算法。先把所有能直接推出终结符的变元标上然后反复扫描产生式只要右部所有符号都被标记过就把左部变元也标上扫到不再有新变元为止最后看起始变元有没有被标上。这个过程一定停机因为变元数有限且标记只增不减这就是它可判定的理由。不可判定的那几个要单独记ALL_CFG文法是否产生全部串、EQ_CFG两台文法是否等价都不可判定。原因不是“文法太复杂”而是这两问需要比较两个语言的全部串归约的源头是计算历史或者波斯特对应问题。另外 A_LBA 是可判定的理由很漂亮线性有界自动机的读写头不能离开输入区所以格局总数被输入长度锁死状态数乘带符号数的带长次方再乘读写头位置数是有限个数跑满这么多步还没接受就说明进入循环直接拒绝即可。顺带记住每一个上下文无关语言都是 P 的因为 CYK 是多项式时间。3.3 真题演练CFL泵引理与CNF转换第一题证明 L {a^n b^n c^n | n ≥ 0} 不是上下文无关语言。用上下文无关语言的泵引理泵长度取 p串取 s a^p b^p c^p。把 s 写成 uvwxy要求 |vwx| ≤ p 且 v、x 不同时为空。因为 |vwx| ≤ p这一段不可能同时横跨 a、b、c 三段最多覆盖两段于是把 v、x 重复之后三段长度的比例一定被破坏得到的串不在 L 里矛盾。踩分点在于“最多覆盖两段”这句话它是整个证明的支点写不出来后面全是空话。第二题把 S → aSb | ε 转成乔姆斯基范式。先处理 ε 产生式因为空串属于该语言保留 S → ε再消单位产生式这道题没有然后引入新变元处理终结符A → aB → b把 S → aSb 改写成 S → ASB最后把右部长度为 3 的产生式拆开引入新变元 CS → ACC → SB。答案写成 S → AC | ε、C → SB、A → a、B → b四步过程每一步都要在卷面上留痕。第三题证明每个上下文无关语言都属于 P。答法是把文法转成乔姆斯基范式然后跑 CYK表格规模是 O(n²)每个表项内部枚举切分点最多 n 次总时间 O(n³)是输入长度的多项式所以该语言在多项式时间内可判定。这道题的价值在于它把“文法”和“复杂度”两章缝在了一起答完顺手写一句“因此上下文无关语言是 P 的子集”分数基本拿满。4. 图灵机与可判定性格局、判定器与不可判定清单4.1 格局、三种停机结果与判定器这三个词的关系格局是图灵机计算过程中某一瞬间的快照由当前状态、当前带内容和读写头当前位置三样东西组合而成三者缺一不可考试里常把“读写头位置”漏掉当干扰项。起始格局是初态加上输入串接受格局是状态为接受状态的那一瞬间。计算历史是一串格局 C1、C2、…、Cl相邻两个格局之间必须符合转移函数确定型机器在任何输入上最多只有一条计算历史非确定型机器可能有多条对应不同的分支。图灵机在输入上跑起来只有三种结局接受、拒绝、循环。循环仅仅指机器不停机不代表它原地重复同样的步骤它可能一直在带子上左右扫、写出越来越复杂的内容只是永远不进接受或拒绝状态。判定器和识别器的区别就卡在这里识别器只保证属于语言的串最终被接受不属于的串可能循环判定器保证所有输入都停机永远能给出接受或拒绝的明确答案所以它才叫“判定”某个语言。这条区分是整章的地基后面的可判定性清单全部建立在它上面。还有几条等价性要背每一个多带图灵机都等价于一台单带图灵机代价是时间平方级变慢非确定型图灵机等价于确定型图灵机代价是指数级变慢每一个可判定语言都是图灵可识别的反过来不成立。丘奇图灵论题说的是“算法”这个直观概念可以用图灵机明确定义它不是一个能证明的定理而是一个被广泛接受的论题考试里出现时答“论题而非定理”往往就是那一分。描述图灵机有三个层次形式化描述要写全状态和转移函数实现描述用日常语言说清步骤但不管带子怎么管高水平描述连图灵机都不提只描述算法本身这三层的区分常考简答。4.2 可判定与不可判定一张表背完别在考场现推语言含义结论A_DFA / A_NFA / A_REXDFA、NFA、正则表达式是否接受某串可判定E_DFA / EQ_DFADFA 是否为空、两台 DFA 是否等价可判定A_CFG / E_CFG文法是否产生某串、文法是否为空可判定A_LBA线性有界自动机是否接受某串可判定A_TM图灵机是否接受某串不可判定其补不可识别HALT_TM图灵机在给定输入上是否停机不可判定E_TM图灵机是否不接受任何串不可判定REGULAR_TM图灵机识别的语言是否正则不可判定EQ_TM两台图灵机是否识别同一语言不可判定且既不识别也不补识别E_LBA / ALL_CFG / PCP线性有界自动机是否为空、文法是否产生全部串、波斯特对应问题不可判定这张表要连着两条定理一起背。第一条一个语言是可判定的当且仅当它既是图灵可识别的也是补图灵可识别的这条把“可判定”拆成了两个方向的枚举是后面很多证明的工具。第二条映射可归约的传递性用法如果 A 映射可归约到 B且 A 不可判定那么 B 也不可判定如果 A 映射可归约到 B且 B 是图灵可识别的那么 A 也是图灵可识别的。归约的方向感必须练到条件反射第 5 章会专门拆这个坑。注意EQ_TM 是整张表里唯一一个“两头都不沾”的语言既不是图灵可识别的也不是补图灵可识别的。看到选项里把它写成“可识别”或“补可识别”直接判错。4.3 真题演练三条不可判定证明的骨架第一题证明 A_TM 不可判定。标准对角线答法假设存在判定器 H输入是“机器 M 和串 w”M 接受 w 时 H 输出接受否则输出拒绝构造新机器 DD 在输入“机器 M”上先跑 H问 M 是否接受自己的描述然后反过来输出——H 说接受就拒绝H 说拒绝就接受把 D 自己喂给 D无论怎么回答都矛盾所以 H 不存在。踩分点在于写清“D 取反”的那一步只写“对角线”三个字拿不到分。第二题证明 HALT_TM 不可判定。答法是把 A_TM 映射归约到 HALT_TM假设有判定停机问题的机器 R用它构造判定 A_TM 的机器 S——S 在输入“M 和 w”上先跑 R如果 R 说不接受直接拒绝如果 R 说接受就模拟 M 跑 wM 接受则接受M 拒绝则拒绝。因为 R 保证了 M 在 w 上一定停机模拟一定结束于是 S 判定了 A_TM与第一题矛盾。这道题的骨架是“先判停机、再模拟”顺序写反就全错。第三题证明 E_TM 不可判定。同样是映射归约从 A_TM 出发给定“M 和 w”构造一台新机器 MM 在任意输入上先忽略输入、直接模拟 M 跑 wM 接受则接受否则拒绝于是 M 接受 w 当且仅当 M 接受至少一个串即 E_TM 的答案为否。用假设的 E_TM 判定器就能判定 A_TM矛盾。这道题的关键在于“M 把所有输入都当成 w 来跑”这个构造考场上要把 M 的行为写清楚不能一句“构造 M”带过。第四题证明一个语言可判定当且仅当它和它的补都图灵可识别。正面方向好证判定器本身就是两台识别器。反面方向是踩分点所在设 M1 识别 LM2 识别 L 的补构造判定器 M 在输入 w 上并行模拟两台机器一步一步交替跑谁先接受就按谁的结果输出。因为 w 要么在 L 要么在补里两台机器必有一台最终接受M 一定停机所以 L 可判定。写“并行模拟、交替一步”这几个字是这道题的核心得分句。5. 失分点排查五类最容易答错的判定与归约题5.1 概念混淆类三个词换一个字答案就翻面第一条把“可识别且补可识别”记成“可识别且可识别”。错在哪看到题面出现两个“图灵可识别”就以为条件已经够了直接下结论“可判定”。为什么错两个识别器都可能在某些输入上循环只有让它们并行跑、谁先停谁说了算才能保证每台机器都会停这个构造正是判定器存在的理由。怎么答对写判定器的时候明确写出“交替模拟每台机器每次只走一步”并补一句“由于 w 必属于 L 或 L 的补两台机器至少有一台接受故必停机”这两句话写全这一分才稳。第二条把可判定和可识别当成一回事在选择题里选了“每个图灵可识别语言都可判定”。错在哪忽略了识别器允许对不属于语言的串循环。为什么错判定要求所有输入都停机识别只要求属于语言的串被接受两者的量词范围不同。怎么答对记住方向可判定一定可识别可识别不一定可判定A_TM 就是可识别但不可判定的标准例子答题时把它抬出来当反例比空谈定义有说服力。第三条把“补图灵可识别”理解成“补集是正则的”或者“补集可判定”。错在哪把“补”这个字和封闭性搞混了。为什么错补图灵可识别只说的是补集能被某台图灵机识别和正则、可判定都没有直接关系。怎么答对见到这个词就在草稿上写一行“L 的补 ∈ RE”然后套第 4 章那条“可判定当且仅当两边都可识别”的定理路径就清楚了。5.2 归约与复杂度类方向写反整道题白做第四条归约方向写反。题目要求证明 B 不可判定答题人却写成“因为 B 可归约到 A_TM所以 B 不可判定”。错在哪箭头方向搞反了把待证问题放在了归约的左边。为什么错映射归约的用法是拿已知不可判定的问题当源头把它归约到待证问题上才能把不可判定性“传染”过去反过来的箭头只能说明 B 能解 A_TM什么也推不出来。怎么答对动笔前先在草稿第一行写“已知难问题 ≤m 待证问题”箭头左边永远是那个已经被证明不可判定的语言右边才是你要证的这一行写完再写构造基本不会错。第五条复杂度层次乱写等号。错在哪把 NL coNL 记成 NP coNP或者把 PATH 写成 NP 完全、把 TQBF 写成 NP 完全。为什么错NL 对补封闭是已经被证明的定理NP 对补是否封闭至今是开放问题两者不能混PATH 是 NL 完全的代表TQBF 是 PSPACE 完全的代表位置完全不同。怎么答对把层次链按顺序默写一遍对数空间在最底层往上依次是非确定对数空间、多项式时间、非确定多项式时间、多项式空间其中非确定多项式空间和多项式空间相等萨维奇定理非确定对数空间和对数空间的补相等而 NP 与 coNP 之间不能画等号只能画问号。6. 复杂度押题P/NP/PSPACE 三层楼怎么定位时间与空间这一章最怕的是把定义背成一团。抓住一个动作就不会乱题目给一个语言先问判定它需不需要“猜”。不需要猜、直接模拟就能在多项式时间跑完的往 P 里放PATH、RELPRIME、以及所有上下文无关语言都在这一层。需要猜一条路径、一个子集、一组赋值但拿到候选答案后能在多项式时间内验证的往 NP 里放HAMPATH、CLIQUE、SUBSET-SUM、SAT、3SAT、UHAMPATH 都是常客。猜完之后还要在多项式空间里做递归或者博弈推演的往 PSPACE 里放TQBF、FORMULA-GAME、GG 是这一层的完全问题。类直观说法代表完全问题与其他层的关系L对数空间可判定基本路径类的细化问题含于 NLNL非确定对数空间PATHNL coNL含于 PP多项式时间可判定不含已知完全问题用归约定义会退化含于 NPNP多项式时间可验证SAT、3SAT、CLIQUE含于 PSPACEPSPACE多项式空间可判定TQBFPSPACE NPSPACE押题方向大致三个。第一类是给语言定位答题模板固定三句说明判定过程需要什么资源给出上界把它放进某个类再用完全问题归约说明它是该类的完全问题。第二类是证明 NP 完全三步走——先证该语言属于 NP给一个多项式时间的验证器再选一个已知 NP 完全问题3SAT 或 CLIQUE 最常用最后构造多项式时间归约并证明两个方向其中“归约函数可在多项式时间内计算”这句一定要写它是很多人漏掉的踩分点。第三类是空间相关的定理萨维奇定理要写对形式对任何满足 f(n) ≥ n 的函数非确定型图灵机的 f(n) 空间可以被子确定型图灵机的 f²(n) 空间模拟正因为平方之后仍是多项式才有 PSPACE NPSPACE 这个结论。归约的经典链条也值得背两条3SAT 多项式时间可归约到 CLIQUE这条常作为构造题出现做法是把每个子句画成一排点同子句内不连边、不同子句间除非文字冲突否则连边然后问是否存在大小为子句数的团列文-库克定理则把 SAT 摆到 NP 完全的中心位置它的常见考法是“SAT 属于 P 当且仅当 P NP”答这句话时不要把它写成“SAT 属于 NP”那是定义不是定理。我自己的血泪经验是每次写归约之前先在草稿最上面单独写一行箭头左边写已知不可判定或已知完全的问题右边写待证问题然后再动笔写构造。这个习惯是被一道 HALT_TM 的题教出来的——那次箭头写反构造写得再漂亮也是零分。后来不管多简单的归约题我都强制先写这一行再展开正确率立刻稳住了。希望帮到你。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
