如何检查我的线路是否与NFA匹配？

Question

我做了NFA，从正则表达式3d数组，例如（01*）表达式。我明白了：

[[FROM,TO,TRANSITION]]

    [['q0', 'q1', '0'], ['q1', 'q2', ':e:'] ,['q1', 'q4', ':e:'] ,
    ['q2', 'q3', '1'], ['q3', 'q2', ':e:'], ['q3', 'q4', ':e:']

如何编写一个方法来测试满足这个自动机的字符串？例如，"011111"将返回q0 q1 q2 q3 q2 q3 q2 q3 q2 q3 q2 q3 q4

Answer 1

1. 您可以将自动机转换为DFA（在检查变得简单之后）。这种方法很有用，因为NFA很小，但是要测试的字符串数量非常大。

2. 您还可以构建一个新的图，其中每个顶点都是成对的（NFA的状态，字符串中的位置）。如果是epsilon跃迁，每个位置的一个态和另一个态之间都有一个边。如果自动机中s->s'转换的字符与字符串中pos位置处的字符匹配，那么还有一个边缘(s, pos) -> (s', pos + 1)。
   在构建图之后，您只需要检查一对(t, string.length())是否至少有一个终端状态t是可到达的（您可以使用任何图遍历算法来检查它，例如深度优先搜索）。