1PDA的控制状态与栈
闭卷重建PDA的控制状态与栈的对象、状态、事件、不变量与一个失败反例。
理论计算：自动机、可计算性与复杂性 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2按终态与按空栈接受
闭卷重建按终态与按空栈接受的对象、状态、事件、不变量与一个失败反例。
3CFG到PDA的构造
闭卷重建CFG到PDA的构造的对象、状态、事件、不变量与一个失败反例。
4PDA到CFG的状态配对变量
闭卷重建PDA到CFG的状态配对变量的对象、状态、事件、不变量与一个失败反例。
5CFL闭包与反例策略
闭卷重建CFL闭包与反例策略的对象、状态、事件、不变量与一个失败反例。
6实验：确定性栈动作
闭卷重建实验：确定性栈动作的对象、状态、事件、不变量与一个失败反例。
7证明：CFG与PDA等价
闭卷重建证明：CFG与PDA等价的对象、状态、事件、不变量与一个失败反例。
第 1 页 · 背面（答案）
核心机制：两种接受方式对NPDA识别能力等价，可通过新起止状态和底标记互相构造；实验入口：把一台空栈接受PDA改为终态接受并证明两方向运行对应；边界：不能在原机上简单把空栈时刻设终态，因为可能还有输入未读。
核心机制：PDA转移同时看控制状态、可选输入符号和栈顶，并用有限串替换栈顶；实验入口：逐步运行识别0^n1^n的PDA，记录剩余输入、状态和完整栈；边界：栈只能直接访问顶部；转移中的ε输入与ε压栈要分辨。
核心机制：变量[pAq]表示从状态p以A为栈顶出发，最终在q弹出A的输入片段；实验入口：为简化PDA列变量和产生式，并解释中间状态枚举为何有限；边界：直接把控制状态当非终结符会丢失栈匹配关系。
核心机制：PDA在栈顶非终结符时非确定选择产生式展开，在栈顶终结符时与输入匹配；实验入口：让PDA模拟S→aSb|ε生成aabb的最左推导；边界：构造证明依赖存在一条正确非确定路径，而非贪心选择产生式。
核心机制：模拟括号和分隔符驱动的push/pop，输出最大栈深或首个非法位置；实验入口：覆盖空栈弹出、未清空、嵌套和混合符号；边界：确定性实现未覆盖NPDA分支；最大深度不是文法复杂度。
核心机制：CFL对并、连接、星、同态和与正则交闭包，但对交和补一般不闭包；实验入口：用与正则语言相交把候选语言切成已知非CFL，再由闭包反推矛盾；边界：一个语言不是正则不能推出它不是CFL；反例必须属于所讨论运算。
核心机制：分别构造CFG到PDA与PDA到CFG，并用推导长度或运行片段做双向证明；实验入口：选一个小文法贯穿两次变换，逐项核对接受语言而非状态名字；边界：只画构造图没有正确性证明不合格；两方向不能互相代替。