我希望在我的词法分析器中实现一个 DFA 最小化器,但我似乎无法生成一个看起来不像它已经是表达式的最小 DFA 的 DFA。
我正在从一个 NFA 构建 DFA,该 NFA 是使用来自后缀正则表达式的 thomson 构造构建的。这和龙书里描述的差不多。为了使词法分析器使用从开始状态的 epsilon 转换来组合几个 NFA。正是在这个组合的 NFA 上应用了 DFA 算法。
那么,是否有任何“已知”的正则表达式会生成一个 DFA,这将为死态消除和状态最小化提供一个很好的测试平台?
我当然可以破解一个奇怪的 DFA 并在其上应用算法,但它真的不是一个合适的测试用例吗?如果这样我构建 DFA 的方法不容易出现死状态,那么该信息将同样有价值,因为那时我可以完全跳过实现状态消除功能。
编辑:如果您需要实现细节以便准确回答,代码可在github上获得,特别是NFA.cs和DFA.cs类。此外,如果有帮助,我还写了一系列关于我正在使用的构造算法的博客文章。