如何生成均勻分佈的隨機DFA？

Question

我需要生成一個確定性有限自動機（DFA），從滿足下列屬性的所有可能的DFA中選擇。必須以均勻分佈的方式選擇DFA。

的DFA必須具有以下四個屬性：

• 的DFA具有N個節點。
• 每個節點有2個傳出轉換。
• 每個節點都可以從其他節點到達。
• 從所有可能性中選擇完全一致的隨機性DFA。

我不考慮標記節點或轉換。如果兩個DFA具有相同的無標籤有向圖，則它們被認爲是相同的。

這裏有三種算法不工作：

算法＃1

1. 啓動了一個名爲A.
2. 組N個節點的選擇從一個節點，並把它放在集B.

3. 雖然有剩餘集A

   - 3.1 Choose a node x from set A 
       - 3.2 Choose a node y from set B with less than two outgoing transitions. 
       - 3.3 Choose a node z from set B 
       - 3.4 Add a transition from y to x. 
       - 3.5 Add a transition from x to z 
       - 3.6 Move x to set B 
   

4. 節點

   對於每個節點n在乙

   - 4.1 While n has less than two outgoing transitions 
       - 4.2 Choose a node m in B 
       - 4.3 Add a transition from n to m 
   

算法＃2

1. 開始與具有N個頂點和無電弧的有向圖。
2. 生成N個頂點的隨機置換以產生一個隨機哈密爾頓週期，並將其添加到圖中。
3. 對於每個頂點，將一個輸出弧添加到隨機選擇的頂點。

算法＃3

1. 開始與具有N個頂點和無電弧的有向圖。
2. 生成一個長度介於N和2N之間的隨機定向循環並將其添加到圖形中。
3. 對於每個頂點，將一個輸出弧添加到隨機選擇的頂點。

我基於算法＃2創建算法＃3，但是，我不知道如何選擇隨機定向週期來創建均勻分佈。我甚至不知道是否有可能。

任何幫助將不勝感激。

Answer 1

如果N很小（滿足前兩個條件的N（2N）個可能的弧集合，所以你希望這個值小於你的隨機數發生器的範圍），你可以生成隨機的DFA，丟棄不滿足可達性條件的那些。