简介《计算理论知识点.docx》是一份面向计算机专业学生、尤其针对哈尔滨工程大学计算理论期末复习整理的知识点速记文档适合需要短期集中背诵、梳理考点的备考者使用。压缩包内共1个docx文件约18KB体量轻便便于打印或在手机、平板上随时翻阅。文档围绕自动机理论、图灵机、语言理论、计算复杂度与其他延伸概念五部分展开以结论式条目罗列正则语言与有穷自动机的等价关系、图灵可识别与可判定语言的区别、判定器与格局的定义、丘奇—图灵论题、映射归约与多项式时间归约、P与NP及SAT、3SAT、CLIQUE等典型问题的归属几乎覆盖期末简答与证明题的常见考点。已有551人学习适合考前对照课堂笔记快速过一遍定义与判定结论补上容易混淆的等价条件和不可判定问题清单。1. 知识地图这门课其实在比“四台机器谁记得多”计算理论期末复习最坑的地方是它看起来像四十多条互不相干的结论背下来也不会串。其实整门课只有一条主线给机器加记忆看它能多认出哪些语言。有穷自动机的记忆只有“当前是哪个状态”下推自动机多了一个栈图灵机多了一条能来回读写的带子最后再把带子加上时间、空间的预算就进入复杂度。每加一层记忆就多一个语言类也多一批封闭运算和可判定问题。所以复习任何一个结论都先问四件事谁识别它、它对哪些运算封闭、它的成员问题可不可判定、要花多少资源。适合已经上过课、手上有讲义但串不起来的人完全零基础直接读会有点跳。2. 语言层级DFA、PDA、图灵机各自认得出什么这一章是整门课的地基。同一个字符串集合换一台更强的机器就能认出来认不出来的原因往往只是“记忆不够”。把每一层都按“识别装置—封闭运算—成员问题”三段来记后面图灵机和复杂度的结论才有地方挂。2.1 正则语言DFA、NFA、正则表达式三方等价有穷自动机是五元组 (Q, Σ, δ, q0, F)状态集合、字母表、转移函数、起始状态、接受状态集合。确定的 DFA 每读一个符号只有一条出路非确定的 NFA 对同一个符号可以有多条出路还能不读符号就跳ε 转移。课上最值钱的一句话是每一台非确定有穷自动机都等价于一台确定型有穷自动机。等价的实现办法是子集构造把“NFA 当前可能处在的状态集合”整体当成 DFA 的一个状态最坏情况下状态数从 n 膨胀到 2 的 n 次方。把三条结论叠起来看就是正则语言的三方等价一个语言被有穷自动机识别则它是正则语言一个语言是正则的当且仅当有一台 NFA 识别它一个语言是正则的当且仅当有一个正则表达式描述它。也就是说 DFA、NFA、正则表达式是同一件事的三种写法考试给哪一种都能转成另外两种。封闭性上必背的三条是并、连接、星号补和交也封闭只是讲义常塞进习题补靠交换 DFA 的接受与非接受状态交靠乘积构造。判断“不是正则”的常用工具是泵引理注意它只能用来证伪不能用来证明一个语言是正则的这个误用率相当高。下面这段把 DFA 的五个参数落到代码里方便对照定义检查自己写的转移表# 用五元组描述 DFA模拟它读完整串的过程 dfa { states: {q0, q1, q2}, alphabet: {0, 1}, delta: {(q0, 0): q1, (q0, 1): q0, (q1, 0): q1, (q1, 1): q2, (q2, 0): q2, (q2, 1): q2}, start: q0, accept: {q2}, } def run_dfa(m, w): state m[start] for ch in w: # 一个符号一步绝不回头 if ch not in m[alphabet]: return False # 出现字母表外的符号直接拒绝 state m[delta].get((state, ch)) if state is None: return False # 转移未定义等价于掉进死状态 return state in m[accept] print(run_dfa(dfa, 1011)) # 只要出现过 11 就停在 q2参数怎么改要换语言就改 accept 和 deltadelta 必须对 Σ 里每个符号都有定义全函数缺的那条要在代码里补一个死状态这正是“确定的机器每一步只有一条路”的具体含义。想把这段改成 NFA只需把 delta 的值换成状态集合运行时维护一个集合而不是单个状态子集构造做的就是这件事。2.2 上下文无关语言文法、下推自动机与乔姆斯基范式上下文无关文法也是四元组 (V, Σ, R, S)非终结符、终结符、规则、起始符号。规则左部永远只有一个非终结符这就是“上下文无关”的字面意思。它对应的机器是下推自动机一台带栈的非确定有穷自动机栈顶决定下一步怎么走。两条方向都要背一个语言是上下文无关的当且仅当存在一台下推自动机识别它如果一个语言被下推自动机识别则它是上下文无关的。乔姆斯基范式是把文法削成极简形式每条规则要么是 A → BC两个非终结符要么是 A → a一个终结符空串另算。结论是任何一个上下文无关语言都可以用乔姆斯基范式的上下文无关文法产生。它的价值不在好看而在于让派生树变成二叉树于是“长度为 n 的串的派生步数”可数、可用动态规划判定CYK 算法就是这么来的。# 检查一个文法是否已经是乔姆斯基范式右部要么两个非终结符要么一个终结符 def is_cnf(g, startS): for lhs, rules in g.items(): for rhs in rules: if rhs (start,) and lhs start and len(rules) 1: continue # 只允许起始符号推出空串 if len(rhs) 2 and all(s in g for s in rhs): continue # A - BC两个都是非终结符 if len(rhs) 1 and rhs[0] not in g: continue # A - a一个终结符 return False return True参数说明g 是“非终结符 → 右部元组列表”的字典判断时要看右部符号是否出现在 g 的键里以此区分终结符和非终结符。很多手写的文法看着像范式其实某条规则右部混了个单非终结符A → B这一步就会返回 False这也是改写成范式时最先要消掉的“单位规则”。封闭性要单独记一笔上下文无关语言在并、连接、星号下封闭但在交和补下不封闭这跟正则语言完全相反是后面易错点那一章的主角之一。2.3 层级关系为什么正则 ⊂ 上下文无关 ⊂ 可判定三层包含关系串起来只有三句话每一个正则语言都是上下文无关的每一个上下文无关语言都是可判定的每一个可判定语言都是图灵可识别的。包含是严格的反例要能张口就来{0ⁿ1ⁿ} 是上下文无关但不是正则{0ⁿ1ⁿ2ⁿ} 不是上下文无关停机问题是图灵可识别但不可判定。语言类识别装置对补/交是否封闭代表判定问题正则语言DFA、NFA、正则表达式补、交、并、连接、星号全部封闭ADFA、ANFA、AREX、EDFA、EQDFA 可判定上下文无关语言下推自动机、上下文无关文法并、连接、星号封闭交、补不封闭ACFG、ECFG 可判定可判定语言递归判定器处处停机的图灵机补封闭ATM 不可判定图灵可识别语言递归可枚举图灵机补不封闭ATM 可识别但不可判定这张表最好自己默写一遍。默写时如果卡在“到底是哪个不封闭”就从机器能力倒推DFA 是有限状态补运算只需翻转接受状态代价为零下推自动机的非确定性无法靠“翻转接受状态”消掉所以补不封闭交也需要两台栈同样出不去。3. 图灵机格局、判定器与可判定语言清单图灵机这一章的结论密度最高但骨架很清晰先把“机器此刻在干什么”形式化再把“机器能否给个准话”分成两档最后把常见问题的可判定性排成一张表。这三步走完第三章和第四章的分界就出来了——判定器存在与否决定了问题落进哪张清单。3.1 格局与三种结局接受、拒绝、循环格局是图灵机计算过程中“当前状态、当前带内容、读写头当前位置”三者的组合。单独说状态没意义单独说带子也没意义必须三者一起才能唯一确定机器此刻的处境。起始格局是开机时的那个格局接受格局和拒绝格局是停机后的那两个格局中间每一步都由转移函数决定。在输入上运行一台图灵机可能出现三种结果接受、拒绝、循环。这里的循环仅仅指机器不停机不是“永远以同样的步骤重复”那个日常语义。由此推出两条常用结论图灵机不接受有两种方式进入拒绝状态或者进入循环如果 M 在 w 上永不停机那么在 M 上既不存在接受计算历史也不存在拒绝计算历史。计算历史就是格局序列 C₁、C₂、…、C_l其中 C₁ 是起始格局C_l 是接受或拒绝格局每个 C_i 都是 C_{i-1} 走一步的结果。计算历史永远是有限序列。确定型机器在任何输入上最多只有一个计算历史非确定型机器即使只有一个输入也有多个计算历史分别对应各个分支——这句是后面证明不可判定性时的关键抓手。# 格局 (当前状态, 带内容, 读写头下标)三者缺一就说不清机器在哪 def step(config, delta, blank_): state, tape, head config if state in (q_accept, q_reject): # 已停机格局不再演变 return config symbol tape.get(head, blank) # 没写过的格子读出来是空白符 write, move, nxt delta[(state, symbol)] # 转移函数一次给出三样东西 tape[head] write # 改写当前格 head 1 if move R else -1 # 读写头左移或右移 return (nxt, tape, head) # 新状态 新带内容 新位置参数说明tape 用字典存“下标 → 符号”所以向左走不需要特殊处理但形式定义里带子是左端有界的真要限制读写头不越界就得另加判断——这正是线性界限自动机的由来。delta 的键是 (状态, 当前符号)值依次是写入符号、移动方向、下一状态。考试让你“描述 M 在 w 上的计算历史”时按这个格式一个个列格局不容易漏项。3.2 识别与判定一字之差隔着一整张清单图灵可识别又叫递归可枚举语言如果一个语言可能被某一台图灵机识别则称它是图灵可识别的。注意“识别”只要求对语言内的串给出接受对语言外的串可以拒绝也可以一直循环。图灵可判定又叫递归语言如果一个语言能被某一台图灵机判定则称它是图灵可判定的。判定意味着对每个输入都停机永远不循环。这类机器叫判定器它总是能决定接受还是拒绝。为什么教材要单独把判定器拎出来因为判定器有时候很难区分“进入循环”和“只是需要耗费很长时间”在理论上你没有任何办法给这两种情况划一条线。所以宁可只讨论所有输入都停机的机器这类机器的行为是可预期的。这条直观解释比定义本身更值得记很多证明题的第一步就是“把 NTM 改成判定器”。四条关系必须成组背每一个可判定语言都是图灵可识别的一个语言是图灵可识别的当且仅当存在非确定型图灵机识别它一个语言是图灵可判定的当且仅当存在非确定型图灵机判定它一个语言是可判定的当且仅当它既是图灵可识别的也是补图灵可识别的。最后一条最容易漏。顺便把“补”的定义补齐一个语言的补是由不在此语言中的所有串构成的语言如果一个语言的补集是图灵可识别的就称它是补图灵可识别的。于是 ATM 的补是不可识别的而 ATM 本身可识别两者一拼可判定性就不成立——这是标准证法。3.3 等价变形与丘奇-图灵论题为什么可以“随手画图灵机”考试里经常出现“多带图灵机”“非确定型图灵机”先别慌它们都不比单带确定型强每一个多带图灵机等价于一个单带图灵机非确定型图灵机也都等价于确定型图灵机。等价是“能识别同样的语言”代价体现在时间上第四章会给出平方和指数的换算语言层面没有区别。丘奇-图灵论题给的是“算法”的明确定义凡是直觉上可计算的都能用图灵机算。它不是一个可证的定理而是整个学科的地基假设所以凡是题目里写“给出一个算法”默认就是“给出一台图灵机”。描述层次要分清三级从低到高层次写法什么时候用形式化描述写全状态集合与转移函数要求“形式化描述”或证明细节时实现描述日常语言说明数据结构怎么摆如“把输入复制到第二条带”大多数构造性证明高水平描述只说算法步骤不提带子和读写头证明可判定性、给归约函数最容易翻车的地方是层次混用前面用高水平描述写了个“把 w 复制一份”后面又突然开始讨论读写头位置读起来像两台机器拼在一起。血泪经验是——一道题里选定一个层次写到底需要细节时再补一句“这一步本文还有配套的精品资源点击获取
-主动抛出异常与错误类型)
