LEON / REFERENCE
计算模型：语言、机器与逻辑
集中回顾核心概念、公式和适用条件。
LEON / LEARNING MAP
先看学习路线
按箭头顺序学习。点击一个阶段进入第一节；完整知识框架列出了每一个主题。
01 / 三个空对象
ε 是空串；{ε} 是含该串的语言；∅ 是没有任何串的语言。每个 Kleene 星都包含 ε。
02 / DFA 设计
用已读前缀满足的性质给状态命名。证明初始情况与每步保持，再将读完全部输入后的状态与接受条件相连。
03 / NFA 接受
一条完整成功运行就够。ε 移动不消耗输入。交换 NFA 接受状态不能求补；须先确定化并补全转移。
04 / 子集构造
从 ε 闭包开始。每个符号先合并全部可能移动，再求闭包。与接受集 F 相交的子集接受。m 个 NFA 状态至多产生 2ᵐ 个子集。
05 / 正则等价
构造接受两台机器意见不同输入的积 DFA，再检查接受状态可达性。对称差为空就等价；到达分歧的路径提供反例。
06 / CNF 与 CYK
文法 CNF 使用 A→BC 或 A→a，并可有受保护的开始符号空串例外。CYK 按跨度递增处理；T[i,j] 表示 w[i:j]，切分满足 i<k<j。
07 / 识别与判定
识别器接受每个成员，但可在非成员上循环。判定器必须在每个输入上停机。单次超时既不能证明拒绝，也不能证明不可判定。
08 / 补语言定理
L 可判定当且仅当 L 与其补都可识别。公平交替运行两识别器，先接受的一方确定正确且终止的答案。
09 / 三种逻辑分类
可满足表示至少一个赋值真；有效表示每个赋值真；不可满足表示无赋值真。k 个原子的穷举真值表有 2ᵏ 个赋值。
10 / 后承检验
Γ 推出 F 当且仅当前提与 ¬F 一起不可满足。反模型使全部前提真而结论假。
11 / 量词纪律
所有 A 都是 B：∀x(A(x)→B(x))。有些 A 是 B：∃x(A(x)∧B(x))。否定交换 ∀ 与 ∃；不同量词的顺序控制见证依赖。
12 / 不可能性证明
假设机器存在，再用重复状态或自指强迫矛盾。一个不终止实现不能证明不可判定；证明必须排除每个可能判定器。