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

Question

我制作了由正则表达式生成3d数组的NFA，例如(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

你可以将自动机转换成(之后检查就变得很简单了)。这种方法很有用，因为NFA很小，但是你要测试的字符串的数量很大。

1. 你也可以构建一个新的图，其中每个顶点是成对的( NFA的状态，字符串中的位置)。如果是epsilon转换，那么对于每个位置，一个状态和另一个状态之间存在一个边缘。如果自动机中用于s->s'转换的字符与字符串中位置pos处的字符匹配，则还有一个边缘(s, pos) -> (s', pos + 1)。

在构建图之后，您只需要检查至少一个终端状态t是否可以访问对(t, string.length()) (您可以使用任何图遍历算法来检查它，例如深度优先搜索)。