DFA 最小化测试套件？

Question

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

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

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

Answer 1

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

Answer 2

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

编辑：

为了扩展我所说的内容，以下是我尝试生成非最小有限自动机测试套件的方法：

1. 使用 N 操作（串联、并集、Kleene 闭包）生成正则表达式。
2. 使用 Kleene 定理中的算法获得其中包含 O(n) 状态的 NFA-lambda。
3. 使用子集/幂集构造来获取其中包含 O(2^n) 状态的 DFA。
4. 重复此操作，直到找到足够数量且足够复杂的自动机。

生成正则表达式更容易。有一些规则：

1. a 是 RE 如果 a 是字母符号
2. (rs) 是 RE 如果 r, s 是 RE
3. (r+s) 是 RE 如果 r, s 是 RE
4. (r*) 是 RE 如果r 是 RE
5. 没有其他东西是 RE

要通过 n 次操作获得 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) + "*)"

您可能会发现非字符串表示（即分层链接结构，本质上是解析树本身）是应用 Kleene 算法获取 NFA-lambda 的更方便的选择。