regex - 生成具有死或多余状态的 DFA 的正则表达式

Question

我希望在我的词法分析器中实现一个 DFA 最小化器，但我似乎无法生成一个看起来不像它已经是表达式的最小 DFA 的 DFA。

我正在从 NFA 构建 DFA，该 NFA 是使用后缀正则表达式中的汤姆森构造构建的。这几乎正​​是龙书中所描述的。为了使词法分析器使用从开始状态开始的 epsilon 转换，将几个 NFA 组合在一起。 DFA 算法正是在这个组合 NFA 上应用的。

那么，是否有任何“已知”的正则表达式会生成一个 DFA，它将为死状态消除和状态最小化提供一个很好的测试平台？

我当然可以编写一个奇怪的 DFA 并在其上应用算法，但这并不是一个真正合适的测试用例，对吗？如果我构建 DFA 的方法不容易出现死状态，那么该信息将同样有值(value)，因为我可以完全跳过状态消除功能的实现。

编辑:如果您需要实现细节以准确回答，代码可在 github 上找到。 ，特别是 NFA.cs和 DFA.cs类。另外我在 blog posts 上写了一个系列关于我正在使用的构造算法，如果有帮助的话。

Answer 1

好的，所以我以一种完全迂回的方式发现了这一点。我制作了一个用于可视化正则表达式的工具，因为我从解析器中得到了相当不错的调试输出。这恰如其分地说明了这样一种表达方式，即使用标准的汤普森构造技术会给你一个非常愚蠢的自动机:(a+b+c+)+|abc
显示在工具中:http://regexvisualizer.apphb.com/?Regex=%28a%2Bb%2Bc%2B%29%2B%7Cabc&NfaSize=300&DfaSize=250#

该工具目前执行直接的 thompson 构造，无需任何优化。如果删除 |abc表达式中完全多余的部分应该保持不变。它没有。