1DFA五元组与逐符号运行
闭卷重建DFA五元组与逐符号运行的对象、状态、事件、不变量与一个失败反例。
理论计算：自动机、可计算性与复杂性 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2从语言条件设计状态语义
闭卷重建从语言条件设计状态语义的对象、状态、事件、不变量与一个失败反例。
3乘积构造：并、交与差
闭卷重建乘积构造：并、交与差的对象、状态、事件、不变量与一个失败反例。
4补语言与完备化
闭卷重建补语言与完备化的对象、状态、事件、不变量与一个失败反例。
5可达状态与等价状态
闭卷重建可达状态与等价状态的对象、状态、事件、不变量与一个失败反例。
6实验：通用DFA模拟器
闭卷重建实验：通用DFA模拟器的对象、状态、事件、不变量与一个失败反例。
7实验：DFA等价短证据
闭卷重建实验：DFA等价短证据的对象、状态、事件、不变量与一个失败反例。
第 1 页 · 背面（答案）
核心机制：状态应代表足够预测未来接受性的历史摘要，先写不变量再画转移；实验入口：为以01结尾、1的个数为偶数两个语言分别提出状态语义并逐边验证；边界：凭图形直觉堆状态会遗漏边界；不同前缀若未来行为不同不能强行合并。
核心机制：DFA由有限状态集、字母表、全定义转移函数、初态和终态集组成，运行是唯一状态序列；实验入口：手推一个二进制值模3自动机，对每个前缀记录余数状态并核对终态；边界：转移缺失就不是完整DFA；终态表示读完整串后的接受而非途经接受。
核心机制：完整DFA交换终态与非终态即可识别补语言，缺失转移必须先指向陷阱状态；实验入口：为一个不完整转移表补陷阱状态，再交换终态并枚举短串对照；边界：直接给NFA翻转终态通常错误；补运算相对于哪个全集必须声明。
核心机制：两个DFA的乘积状态同步记录两台机器状态，终态布尔条件决定并交差与对称差；实验入口：构造奇数个1且以0结尾的乘积机，运行四条边界串；边界：两个自动机字母表与转移完备性需先统一，终态条件不能照抄。
核心机制：读取转移表、终态与输入串，逐符号输出最终状态和ACCEPT/REJECT；实验入口：测试空串、陷阱循环、长前缀和非法符号；边界：模拟器结果只能验一个实例，语言正确性还需状态不变量证明。
核心机制：删除不可达状态保持语言，等价状态则对所有后缀给出相同接受结果；实验入口：先BFS标可达，再用区分表从终态/非终态对开始反向传播；边界：不可达与可合并是两个问题；只比较当前是否终态不足以判等价。
核心机制：在乘积图寻找一边终态一边非终态的最短可达状态对，输出区分串或EQUIVALENT；实验入口：BFS按字母顺序展开以稳定得到最短字典序证据；边界：在有限测试集上结果一致不能证明等价，必须覆盖整个乘积可达图。