algorithm - 什么是 McNaughton-Yamada 算法？

Question

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

我很困惑，因为在我们在类里面找到 DFA 后，我的导师展示的最小化例程似乎与我们 book 中描述的“标记”最小化没有任何不同。 .

感谢您的回复，

内森

Answer 1

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