(相关资料图)

Myhill-Nerodo Theory (MN)：

每个正则表达式都有且只有有限个 equivalence classes。且其可以被表达为唯一的最小有限自动机 (Minimal DFA)。

根,据 MN，我们可以得到一个思路框架：1. 得到正则语言对应的最小 DFA；2. 使用编程语言实现有限自动机；3. 找出最长前缀 (Prefix)

关于第一步：得到正则语言 L 对应的最小 DFA(L)

可以有两种方法：

找出 equivalence classes 并直接根据 MN 构建最小 DFA；

根据 Thompson's Construction Steps 得到对应的 NFA with epsilon transition（带有 epsilon转移的不确定的有限自动机）。去掉 epsilon transition 后可得到 normal NFA。normal NFA 可以轻松转换成 DFA。最后使用 MN 将其化简为 minimal DFA。