java - 将 DFA 实现为链表的算法

Question

我想知道如何在 C/C++/Java 中将 DFA 实现为链表。

Answer 1

由于每个状态都可以有多个分支，因此您可能需要多个链表。这意味着，每个状态都有一个由 n 个链表组成的数组。所以它更像是一个带有循环的树结构，而不是一个简单的链表。

Answer 2

这绝对是可能的，但效率极低。您要做的是将所有状态简单地存储在链接列表中，然后每个状态都需要保留一个转换表。转换表看起来像：

'a' -> 2
'b' -> 5

您的字母表在哪里{a,b}，而 2 和 5 是存储在链接列表中位置 2 和 5 的状态。正如我所说，这绝对不是您想要实现 DFA 的方式，但它是可能的。

Answer 3

我首先想到的是，

使用两个数组组件创建一个名为state的类/结构。一种用于可以到达我们州的状态，另一种用于可以从我们州到达的状态。然后创建一个链表，其元素是您的状态。

这是我对这个类的实现

class state
{
    private:
        string stateName;
        vector<state> states_before_me;
        vector<state> states_after_me;
        state* next;

        //methods of this state

}

Answer 4

单链表不能有效地表示 DFA。您可以将 DFA 视为有向加权图数据结构，因为状态是顶点，转换是边，转换符号是权重。有两种主要的方法来实现图结构。

i) 邻接表：它基本上有 V（顶点数）链表。每个链接列表都包含与相应顶点有边的顶点。如果我们有顶点(1,2,3)和边(1,2),(1,3),(2,1),(2,3),(3,3)对应的邻接列表是：

1->2->3
2->1->3
3->3

ii) 邻接矩阵：它是一个 VxV 矩阵，在 (i,j) 处的每个条目都表示从 i 到 j 的边。上面的相同示例表示为（1 表示有边缘，0 表示没有）：

  1 2 3
1 0 1 1
2 1 0 1
3 0 0 1

但是您必须对这些进行少量更改，因为您的图表是加权的。

对于列表实现，您可以将链接列表中的顶点更改为包含顶点和连接这些顶点的边的权重的结构。

对于矩阵实现，您可以将权重直接放入矩阵而不是 0,1 值。

如果您不想处理图形类的实现，那么有像 Boost Graph Library 这样的库，其中包含两个实现和所有重要的图形算法 DFS 到 Dijkstra 的最短路径算法。您可以从http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/index.html查找它。