常規語言的最小抽吸長度

Question

如何計算常規語言的最小抽吸長度。例如，如果我有0001 *，那麼這個最小抽吸長度應該是4，即000不能被泵送。爲什麼是這樣？

Answer 1

它將小於或等於該語言的最小DFA中的狀態數減1。因此，將正則表達式轉換爲DFA，將其最小化並計算狀態。例如：

0001* 

SOURCE SYMBOL DESTINATION 
q1  0   q2 
q1  1   q5 
q2  0   q3 
q2  1   q5 
q3  0   q4 
q3  1   q5 
q4  0   q5 
q4  1   q4 
q5  0   q5 
q5  1   q5 

這是爲什麼？因爲這是您可以在DFA中執行的最大轉換次數，而無需訪問某個狀態兩次。一旦你兩次訪問一個國家，你已經循環。

當然，語言的最小DFA可能缺少該長度的路徑。在這種情況下，您可以通過使用深度優先搜索自動機的圖形以及查看可以跟蹤的路徑多長時間，找到兩次未訪問狀態的最長路徑（從開始狀態開始）。那將是你真正的答案。