2

我需要为 CS 类使用 McNaughton-Yamada 算法构建 DFA。问题是算法是补充材料，我不清楚它到底是什么。它是一种在给定 RegEx 的情况下找到 DFA 的方法，还是找到 DFA 并最小化它？我似乎找不到有关该主题的任何信息。

我很困惑，因为我们在课堂上发现 DFA 后我的老师展示的最小化例程似乎与我们书中描述的“标记”最小化没有任何不同。

感谢您的回复，

弥敦道

4

3 回答 3

6

在http://swtch.com/~rsc/regexp/regexp1.html上有算法的描述（对于 NFA 和 NFA 到 DFA 的正则表达式）；他们展示了 Thompson 的版本，并声称 McNaughton-Yamada 算法基本相同，但直接从正则表达式生成 DFA。

于 2011-03-10T03:21:32.323 回答
2

“... McNaughton-Yamada 分析算法，其中找到一个正则表达式来描述有限状态机接受的词，该有限状态机给出了转换表。未经修改的算法将产生代表 n 状态机的 4n 个项。这个数字可以是“通过消除重复计算和拒绝对应于同一状态图中没有可能路径的高级表达式来减少。剩余的表达式存在严重的简化问题，因为空表达式和空词是由算法自由生成的。”

来源

于 2011-03-10T03:23:37.517 回答
2

他们的算法通常不会与汤普森的工作分开提出。Thompson 的原版从正则表达式变成了内存中的模拟 NFA。Thompson-McNaughton-Yamada 算法是一个扩展，它将正则表达式转换为存储在内存中的实际 NFA，而不是瞬态模拟。

将 NFA 转换为 DFA（确定）不是 McNaughton 或 Yamada 扩展的一部分。相反，它是通过子集构造（又名幂集构造）算法完成的。

您可以使用 Compiler Construction Toolkit 的NFA 和 DFA 正则表达式工具查看 Thompson-McNaughton-Yamada 算法和子集构造算法对任意正则表达式的作用。

于 2012-05-08T06:00:46.313 回答