计算理论期末复习：自动机判定表与一句话知识点答题骨架

简介《计算理论知识点.docx》面向准备计算理论期末复习的高校学生尤其适合哈尔滨工程大学相关课程考生用来应对概念多、结论杂、考前需要集中背诵的问题。内容沿自动机理论、图灵机、语言理论与计算复杂度四条主线整理高频考点涉及正则语言在并、连接和星号运算下的封闭性确定型与非确定型有穷自动机等价图灵可识别与图灵可判定语言、判定器、乔姆斯基范式、映射归约、P类与NP类、SAT与3SAT等常考结论并突出“先背结论再理解”的复习路径。压缩包内共1个docx文件约18KB篇幅紧凑便于打印成册或导入平板随时翻阅。已有553人学习可作为课堂笔记之外的提纲式材料帮助读者快速建立概念对应关系、定位薄弱章节并在考前完成一轮高频知识点复盘。1. 分数从来不平均这门课真正拉开差距的是「一句话知识点」计算理论期末的卷面结构往往和复习时的直觉相反。对角线法那道大题只要写出「反证假设存在判定器 H」和「构造 D让 D 在 ⟨D⟩ 上自我矛盾」两句话过程分基本就拿到了真正批量扣分的是填空、判断和简答里的那些一句话知识点「每一个正则语言都是上下文无关的」「每一个可判定语言都是图灵可识别的」「EQ_TM 既不是图灵可识别的也不是补图灵可识别的」。这些点没有推导空间对就是对错就是整题没有。所以复习顺序应该是倒着来先把等价关系和可判定性清单背到条件反射再回头攻构造题和归约证明。这门课适合的复习方式不是刷题海而是把每个模块的「定义—等价刻画—判定结论」三件套按顺序默写一遍写不出来的地方就是考场上会卡住的地方。下面按模块拆每一块都给高频问法、能照着写的答题骨架以及最容易出问题的位置。2. 正则语言DFA、NFA、正则表达式通向同一张判定表2.1 三种等价刻画先认清谁等于谁正则语言这一块的所有题本质都在考同一组等价关系被 DFA 识别、被 NFA 识别、能用正则表达式描述、是正则语言这四个说法其实说的是同一件事。考试里任意两个之间都能出成判断题或者证明题答题时把它们当成同一个集合的四种写法思路就不会乱。DFA 是五元组 (Q, Σ, δ, q₀, F)δ 一步只给一个去向NFA 多出来的是 ε 转移和一个状态对同一符号的多个去向δ 的值域变成状态集合。卷面上让你「构造一台 DFA 接受 L」只要语言里出现「模几计数」「第几个字符是某符号」「包含或不包含某子串」这类特征基本就是有限状态能解决的信号如果语言要求「0 的个数和 1 的个数相等」那就该怀疑它不是正则的往下走泵引理。最常考的一个例子L {w ∈ {0,1}* | w 中 1 的个数是偶数}。两个状态就够。状态读入 0读入 1→ q₀接受q₀q₁q₁q₁q₀表里箭头标初态接受状态要单独注明。卷面上画状态图最容易漏的就是给 F 打标记图画对了、F 没标一样扣分。NFA 转 DFA 用子集构造把 NFA 的状态集合整体当作 DFA 的一个状态起点取 {q₀} 的 ε-闭包然后对每个符号求像再取一次 ε-闭包直到不再出现新集合。状态数上限是 2ⁿ卷面题一般三到五个状态手算推得完。这里有两个固定扣分点ε-闭包只在开头取了一次忘了「求像之后还要再取」空集状态 ∅ 出现了却不写进状态表。∅ 是合法状态它读任何符号都回到自己漏了它转移函数就不完整。2.2 封闭性能直接拼出答案的一条捷径正则语言在并、连接、星号三种运算下封闭这三条是必背的。补、交、差、反转其实也封闭出题人很喜欢把它们混在一起考问「下列哪种运算下正则语言不封闭」选项里塞一个「同态原像」或者干脆全是封闭的让你不敢选。封闭性的价值不在背结论在于它能当构造工具用。题目给两台 DFA让你证明 L(A) ∪ L(B) 是正则的标准答法不是重新设计状态机而是加一个新初态用 ε 分别指向两台机器的初态接受状态取两者的并。连接就从前一台的每个接受状态拉 ε 到后一台的初态星号是加新初态、新接受状态再让老接受状态 ε 回到老初态。这三句话写清楚比画一张大图省时间也更不容易错。补运算要注意一个细节DFA 必须是「完全」的也就是每个状态对每个符号都有转移否则取补时会把「没有转移」当成接受。答题时先补一个死状态把转移补齐再交换接受状态集合这一句写上去阅卷就知道你懂。提示封闭性证明题里只要出现了「新初态 ε」这个结构就要明说新初态不是接受状态否则星号运算会接受空串以外的串结论就错了。2.3 泵引理它只能用来证否方向不能反泵引理的表述是若 L 是正则语言则存在泵长 p对任意长度不小于 p 的串 s ∈ L都能写成 s xyz满足 |y| ≥ 1、|xy| ≤ p并且对任意 i ≥ 0 都有 xyⁱz ∈ L。这段话里每一个量词的位置都是考点尤其是「存在 p」和「任意 s」的先后顺序写反了整题作废。用它证否的答题模板固定四步。第一步假设 L 是正则的取泵长 p。第二步自己挑一个长度不小于 p 的串 s挑的原则是让所有可能的拆分都走向矛盾。第三步说明对任意满足 |y| ≥ 1 且 |xy| ≤ p 的拆分 xyz取某个 i 得到一个不在 L 里的串。第四步得出矛盾L 不是正则的。拿 L {0ⁿ1ⁿ | n ≥ 0} 走一遍取 s 0ᵖ1ᵖ。因为 |xy| ≤ p而 s 的前 p 个字符全是 0所以 y 只可能由 0 组成。取 i 2 得 0^(p|y|)1ᵖ0 的个数多于 1 的个数不属于 L。关键那句是「由于 |xy| ≤ py 中不可能同时含有 0 和 1」这句话不写分就断在这里。反过来想证明一个语言是正则的泵引理一点用都没有。它是必要条件不是充分条件。「泵引理能泵」推不出「正则」这个逻辑方向每年都有人搞混。要证是正则的老老实实构造 DFA、写正则表达式或者用封闭性从已知正则语言拼出来。2.4 真题演练A_DFA、A_NFA、A_REX 为什么都可判定这一组题的问法很固定「证明 A_DFA {⟨B, w⟩ | B 是 DFA 且 B 接受 w} 是可判定的」。分值通常 8 到 10 分评分看的是判定器的四步写没写全。A_DFA 的判定器在输入 ⟨B, w⟩ 上先检查编码是否合法不合法直接拒绝然后从 B 的初态出发按 w 的每个符号逐步更新当前状态w 读完后若当前状态属于 F 就接受否则拒绝。因为 w 有限每步只走一个状态机器一定停机所以这是判定器不是识别器。这句「一定停机」必须写很多人只写了模拟过程没写停机性等于没证明可判定。A_NFA 的判定器不一样。NFA 的「接受」是存在一条接受路径你不能直接在 NFA 上跑因为要判断「所有分支都走完了还没有接受路径」需要遍历完整个分支树。标准答法两步先用子集构造把 NFA 转成等价的 DFA再跑上面的模拟。也可以直接模拟状态集合维护一个「当前可能处于的状态集合」读完 w 后看这个集合和 F 有没有交集。A_REX 的判定器把正则表达式按归纳法转成等价 NFA原子情形 R a 造两个状态一条边R ∅ 造一台不接受任何串的机器R ε 造一条 ε 边归纳情形分别对应并、连接、星号三种拼法。转完再跑 A_NFA 的判定器。还有两个常考的变体。E_DFA {⟨A⟩ | A 是 DFA 且 L(A) ∅}用可达性搜索从初态出发反复标记能到达的状态停机后看有没有接受状态被标记到有就拒绝没有就接受。EQ_DFA {⟨A, B⟩ | L(A) L(B)}先构造对称差机器 C让 L(C) (L(A) ∩ L(B)ᶜ) ∪ (L(A)ᶜ ∩ L(B))再跑 E_DFA。这两道题的共同套路是「把新问题归约到已经解决的老问题上」这句话写在证明开头比直接闷头写状态机更像标准答案。3. 上下文无关语言CFG、PDA、乔姆斯基范式三件套3.1 CFG 与 PDA 的等价双向证明的骨架怎么写语言是上下文无关的当且仅当存在一台下推自动机识别它。这条等价是这一章的地基也是简答题的常客。CFG 是四元组 (V, Σ, R, S)产生式形如 A → αPDA 是六元组 (Q, Σ, Γ, δ, q₀, F)δ 把「状态 × 输入符号或 ε × 栈顶符号或 ε」映到「状态 × 栈顶替换串」的集合。两个方向都有固定骨架。CFG 到 PDA只留一个状态先把起始变元 S 压栈然后反复做三件事——栈顶是变元就非确定地选一条产生式把右部反向压栈栈顶是终结符且和当前输入符号相同就弹栈并前进一格栈空了且输入读完就接受。核心句子是「反向压栈保证最左推导的顺序」写了这句说明你知道为什么是反着压。PDA 到 CFG先把 PDA 简化成三状态形式一个起始状态、一个循环状态、一个接受状态所有栈操作都在循环状态上完成。然后为每一对状态 (p, q) 设一个变元 A_pq含义是「从 p 到 q 且净弹出一个栈符号的所有串」。转移的三种情况分别对应三条产生式规则最后把起始变元设成 A_{q₀,q_accept}。这个方向写起来长考试里一般只要求说清「三状态简化 变元 A_pq 的含义 三种转移对应的产生式」不要求把每条产生式列全。顺带把层次关系记牢每一个正则语言都是上下文无关的反过来不成立{0ⁿ1ⁿ} 就是最好的反例。这条判断题几乎年年有选项常写成「上下文无关语言在补运算下封闭」之类的干扰项——CFL 在并、连接、星号下封闭但补运算下不封闭这一点和正则语言不同非常容易混。3.2 乔姆斯基范式为什么非要转成这个形状乔姆斯基范式要求所有产生式只有两种形式A → BC右部恰好两个变元A → a右部恰好一个终结符。另外允许起始变元 S → ε但 S 不能出现在任何产生式的右部。转换分四步顺序不能换。第一步加一个新起始变元 S₀ 和产生式 S₀ → S这是为了保护后面可能出现的 S → ε。第二步消 ε 规则先找出所有「可空变元」也就是能推导出 ε 的变元反复迭代直到集合不再变大然后对每条产生式枚举删掉可空变元的所有组合补出新规则最后删掉所有 A → εS₀ → ε 除外。第三步消单位规则 A → B对每个变元求它的「单位闭包」把 A → B 替换成 A 直接指向 B 能推出的所有非单位产生式。第四步拆长规则右部超过两个符号的用新变元二分右部混杂终结符和变元的先把每个终结符换成一个专属变元。为什么要费这个劲因为只有乔姆斯基范式才能保证长度 n 的串n ≥ 1的任何推导恰好是 2n − 1 步。这个步数上界是 A_CFG 可判定的核心依据答题时把这句话点出来比列一堆产生式有用得多。注意转换完成后一定要回头检查起始变元有没有出现在右部以及每条产生式是不是严格符合那两种形式。这两条不满足2n − 1 的结论就不成立后面的判定性证明跟着一起塌。判断一个串能不能被文法派生用 CYK 算法填三角表。令 V[i, j] 是从第 i 个字符到第 j 个字符这段子串能被哪些变元派生出来。长度 1 直接查 A → a长度大于 1 就枚举拆分点 k把所有满足「A → BC 且 B ∈ V[i, k] 且 C ∈ V[k1, j]」的 A 放进 V[i, j]。拿文法 S → ABA → AA | aB → BB | b 和串 aabb 走一遍n 4| i \ j | 1: a | 2: a |本文还有配套的精品资源点击获取