DFA最小化测试套件？

我正在寻找确定性有限自动机的测试套件，用于测试DFA最小化算法的正确性。你能给我一些指点吗？或者有没有可以产生这种自动机的算法/实现？DFA最小化测试套件？

为了赢得赏金，您需要提交一个400或更多不同大小和复杂度的非最小自动机的测试套件，至少20个包含2000多个节点。

如果这是不正确的地方问这个问题，请指导我到一些更好的地方。谢谢。

来源

2012-01-18 ShyPerson

出于好奇，你对测试性能或正确性感兴趣吗？或两者？或者是其他东西？ – Patrick87 2012-01-18 19:45:02

感谢您的写作。我对正确性感兴趣。 – ShyPerson 2012-01-19 04:55:21

我已将您的评论纳入编辑。谢谢 – ShyPerson 2012-01-21 04:30:29

要测试正确性，您可以尝试将最小的DFA转换为OpenFst格式，并使用equivalence操作测试最小化的加密因子的等价性。

来源

2012-01-18 21:24:10

我错过了什么吗？我可以看到这个漂亮的工具如何验证最小化的自动机，但是我看不到最初的非最小化自动机来自哪里。 – ShyPerson 2012-01-19 05:00:35

测试“所有”DFA到n个状态和m个字母符号是不可行的。你可以用已知的最小DFA测试DFA; （DFA，最小DFA）对，您可以生成随机RE，使用Kleene定理获得算法的NFA-lambda，使用子集构造获得DFA，然后使用已知的正确DFA最小化算法最小化（我假设您接受规范算法是正确的）。

编辑：

为了扩大对我说，这里的如何我会尝试生成非最小有限自动机的测试套件：

生成使用N个操作的正则表达式（串联，工会，Kleene关闭）。
使用Kleene定理的算法得到一个带有O（n）状态的NFA-lambda。
使用子集/ powerset构造来获取其中具有O（2^n）个状态的DFA。
重复，直到找到足够多的足够复杂的自动机。

生成正则表达式更容易。有几个规则：

一个为RE如果a是一个字母符号
（RS）为RE如果r，s为的RE
（R + S）是一个RE如果r ，S为Res
（R *）是一个RE如果R是RE
没有别的是RE

要获得与正操作的RE，递归方法工作。

GetRE(ops) 
1. if ops = 0 then return RandomAlphabetSymbol() 
2. select(Rand() % 3) 
3. case 0 then 
4. ops1 = Rand() % (ops - 1) 
5. ops2 = (ops - 1) - ops1 
6. return "(" + GetRE(ops1) + "+" + GetRE(ops2) + ")" 
7. case 1 then 
8. ops1 = Rand() % (ops - 1) 
9. ops2 = (ops - 1) - ops1 
10. return "(" + GetRE(ops1) + "." + GetRE(ops2) + ")" 
11. case 2 then 
12. return "(" + GetRE(ops - 1) + "*)"

您可能会发现一个非字符串表示（即分级联结构，基本语法树本身）是应用克林的算法得到NFA-拉姆达一个更方便的选择。

来源

2012-01-19 05:03:45 Patrick87

DFA最小化测试套件？

回答

相关问题