有限自动机与正则语言

DFA 与 NFA 的定义与子集构造等价性、正则表达式与自动机的相互转换、泵引理证明非正则性、DFA 最小化。本章还讲词法分析器就是一个 DFA。

本章要点

• NFA 到 DFA 可能指数爆炸
• 泵引理是证明”不是正则”的工具
• 正则语言在并、交、补下封闭

相关阅读

• 字符串算法

写作状态

本章目前为提纲，正文待撰写。