第3周 星期二 第2大节

• 视频：screen_编译原理与设计_第3周_星期二_第2大节.mp4
• 字幕：transcripts/第3周_星期二_第2大节.srt

时间轴

• 01:06 复习：DFA/NFA五元组对比
• 08:19 ε-闭包详细计算示例
• 14:44 子集构造法流程（矩阵迭代→闭包→重命名）
• 16:06 NFA→DFA示例1（单符号A）
• 24:08 NFA→DFA示例2（{0,1}，无ε边）
• 30:31 DFA最小化动机（状态少→效率高）
• 32:42 最小化两步：删除不可达状态+合并等价状态
• 36:00 不可达状态检测（DFS遍历）
• 44:17 划分法合并等价状态（含多个示例）
• 01:21:14 定理：正规式↔有限自动机等价
• 01:23:35 充分性：NFA→正规式（3条替换规则）
• 01:31:53 必要性：正规式→NFA（3条规则逆用）
• 01:41:06 完整流程：RE→NFA→DFA→最小化DFA
• 01:55:51 词法分析器设计：属性字、符号表、输入缓冲、预处理、状态图构造、扫描器实现

关键点

考勤/签到/小测

无。

作业

• 02:25:55 乐学有作业和测验——“大家记得按时完成，千万不要过了”

考试/复习重点

• ⚠️ 23:26 NFA→DFA不会单独考大题，会嵌入复杂多步骤题中，前步错则全题错
• 32:12 DFA最小化对实际实现的内存效率很重要
• 等价状态定义：∀字符串ω，从两状态出发最终同接受或同拒绝（34:17）
• 划分法初始划分：终态集+非终态集（44:17）
• 正规式↔NFA↔DFA↔最小化DFA全流程（01:41:06）
• 词法分析器两种实现：数据驱动（表驱动法）vs程序驱动（程序中心法）

其他需要回看的片段

• 16:06-22:50 NFA→DFA子集构造法完整示例（单符号A）
• 24:08-29:37 NFA→DFA示例（双符号{0,1}，无ε边）
• 44:17-01:06:34 划分法多示例（3状态→2状态、7状态→5状态）
• 01:23:35-01:31:20 NFA→正规式三条替换规则

省流

密度最高的一节。覆盖NFA确定化（子集构造法）、DFA最小化（划分法）、正规式与有限自动机等价证明、词法分析器实现方法。⚠️ 考试重点：NFA→DFA通常嵌入大题，前错全错。