从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]