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最小化測試套件？

回答

相關問題