從DFA中提取語言的算法

Question

我正在嘗試查找從DFA中提取語言的算法。如果該語言是無限的，那麼我只需要報告：maxcount < = 1000個字符串。對於報告的順序沒有限制。

我曾嘗試：（我不知道怎麼寫算法，所以我只是在口頭上我做了什麼解釋）

遞歸算法 - 每次轉換從一個狀態到下一個狀態/狀態保存轉換字符，然後對每個轉換進行遞歸調用，如果該轉換處於接受狀態，則報告。如果我們已經達到「死路一條」，那麼就要記錄遞歸。

假設開始狀態是state 1並且有兩個轉變到：state 2和state 3分別與過渡字符'a'，'b'。然後，從state 3到state 4的轉換與轉換字符'c'，只有state 4是接受狀態。

從state 1到state 2去將給節省'a'過渡人物，但由於state 2是一條死衚衕會有指出改乘上，因爲它不接受狀態則有提至報告。

從state 1到state 3走向將節省'b'，然後從state 3到state 4去將節省'c'讓我們有一個總的"bc"，自state 4沒有遞歸結尾的任何轉變。我們報告"bc"因爲state 4是接受狀態

---

如果我有DFA與環 - 那麼爲了在循環不就是「被困」我已經確定，「如果」存在另一種可能的過渡那麼我們始終會選擇這一轉變，而不是我們做最後一次轉換/次，我們在那裏在那個狀態（一種存貯器進行過渡，我們提出各國在這）

該算法適用於小型的DFA但它會給在更大的DFA上發生堆棧溢出：（想象從state 1到state 2的20個轉換和從state 2轉換到的30個轉換等）。

有人可以推薦更高效的算法嗎？

Answer 1

注意：我猜你可以將這個問題建模爲查找所有啓動狀態和所有接受狀態之間的路徑。所以，我相信這可以通過深度優先搜索圖來完成。深度優先搜索將查找兩個節點之間的所有非循環路徑。

如果您熟悉Depth First Search (DFS)算法，這是一種圖搜索/遍歷算法可以幫助您解決問題。讓我給你一個非常簡單的例子。給定一個有向圖，源頂點'和目的頂點'd'，打印所有從給定's'到'd'的路徑。考慮下面的有向圖。讓s爲2，d爲3.從2到3有4條不同的路徑。

的想法是做給向圖的Depth First Traversal。從源頭開始遍歷。繼續將訪問的頂點存儲在數組中，例如path[]。如果我們到達目的頂點，打印path[]的內容。 重要的事情是將path[]中的當前頂點標記爲已訪問，以便遍歷不會進入循環。

示例代碼：您可以在Javahere一個非常簡單的代碼，找出在圖中，兩個節點之間的所有路徑。

Answer 2

1. 運行一個週期檢測算法。
2. 如果沒有循環，則運行任何路徑搜索算法（BFS，DFS，Dijkstra，A *等）以列出從開始到結束的所有路徑。
3. 如果存在循環運行尋路以查找從起始節點到循環的路徑。然後輸出（開始節點到循環）+（從連接節點開始的循環）* N，對於N = 1,2,3，...，1000。

或者：

1. 轉換爲正則表達式。
2. 從正則表達式生成單詞。

Answer 3

我會在DFA上進行廣度優先搜索來做到這一點，它會產生按長度排序的字符串。

定義由國家和一個字符串的對象（還有一個內存更有效的解決方案在這裏，但我認爲，如果你只需要生產1000串，這將是罰款）​​。然後創建這樣的對象的工作隊列。使用狀態爲開始狀態且字符串爲空的單個對象初始化工作隊列。

現在重複以下三個步驟，直到找到maxcount串或隊列變空：

1. 隊列中刪除第一個對象。

2. 如果其狀態爲接受狀態，則輸出其字符串。

3. 對於每個可能的過渡（包括一個字符和一個新狀態），在隊列的末尾添加一個具有過渡狀態的新對象以及對象字符串與過渡字符的連接。

Answer 4

如果您使用BFS，則循環無關緊要。這個想法是定義包含當前狀態的搜索節點和指向前任節點的指針。因此，當您訪問接受狀態的節點時，可以向後追溯前面的指針以確定接受的字符串（反向）。事實證明，如果一個搜索節點也包含導致從前一個節點狀態到當前狀態的轉換的字符，那麼它會很優雅。

以下是一個Java的方法：

import java.util.ArrayDeque; 
import java.util.ArrayList; 
import java.util.Deque; 
import java.util.HashMap; 
import java.util.List; 
import java.util.Map; 
import java.util.Map.Entry; 

class Experimental { 
    // DFA state with its transitions, possibly accepting. 
    static class State { 
    final Map<Character, State> transitions = new HashMap<>(); 
    final boolean accept;  
    State(boolean accept) { 
     this.accept = accept; 
    } 
    } 

    // A little DFA. 
    static final State s0 = new State(false); 
    static final State s1 = new State(false); 
    static final State s2 = new State(true); 
    static final State s3 = new State(true); 
    static { 
    s0.transitions.put('a', s1); 
    s0.transitions.put('b', s2); 
    s0.transitions.put('c', s3); 
    s1.transitions.put('d', s3); 
    s2.transitions.put('e', s0); 
    s2.transitions.put('f', s1); 
    } 

    // An enumerator of strings accepted by the DFA in order of length. 
    static class Enumerator { 
    static class Node { 
     final Node prev; 
     final char prevCh; 
     final State state; 
     Node(State start) { 
     this(null, Character.MIN_VALUE, start); 
     } 
     Node(Node prev, char ch, State state) { 
     this.prev = prev; 
     this.prevCh = ch; 
     this.state = state; 
     } 
    } 

    final Deque<Node> queue = new ArrayDeque<>(); 
    final List<String> output = new ArrayList<>(); 
    final State start; 

    Enumerator(State start) { 
     this.start = start; 
    } 

    Enumerator enumerate(int outputLimit) { 
     queue.clear(); 
     output.clear(); 
     // Enqueue a search node for the start state. 
     queue.add(new Node(start)); 
     while (!queue.isEmpty() && output.size() < outputLimit) { 
     Node current = queue.pollFirst(); 
     if (current.state.accept) { 
      // Follow prev pointers to build the accepted string. 
      StringBuilder sb = new StringBuilder(); 
      for (Node p = current; p.prev != null; p = p.prev) { 
      sb.append(p.prevCh); 
      } 
      output.add(sb.reverse().toString()); 
     } 
     // Enqueue nodes for the successors of current state. 
     for (Entry<Character, State> transition : current.state.transitions.entrySet()) { 
      queue.addLast(new Node(current, transition.getKey(), transition.getValue())); 
     } 
     } 
     return this; 
    } 
    } 

    public static void main(String[] args) { 
    System.out.println(new Enumerator(s0).enumerate(20).output); 
    } 
} 

輸出：

[b, c, ad, beb, bec, bfd, bead, bebeb, bebec, bebfd, bebead, bebebeb, bebebec, bebebfd, bebebead, bebebebeb, bebebebec, bebebebfd, bebebebead, bebebebebeb]