如何检查我的线是否与NFA相符？

我制作了来自正则表达式3d数组的NFA，例如（01 *）表达式。我得到它：如何检查我的线是否与NFA相符？

[[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

来源

2017-04-16 Eywa

那么，如果自动机是确定性的，你会知道该怎么做吗？ – timgeb

（如果是的话，将搜索引擎foo应用于构建DFA的算法） – timgeb

您可以使用很多现有的库，因此您不必重新编写该weel。我建议使用http://www.brics.dk/automaton/，这是一种适用于Java的工业强度，易于使用的自动机包。它确实是你想要的。如果您需要更多关于为了匹配给定字符串而采取的特定转换的更多信息，扩展Automaton类也很容易。 – Julian

您可以将自动转换为DFA（后检查变得微不足道）。这种方法很有用，NFA很小，但你要测试的字符串数量非常大。
你也可以建立一个新的图形，其中每个顶点是对（NFA的状态，在字符串中的位置）。如果它是一个epsilon转换，每个位置的状态和另一个状态之间有一个边界。如果自动机中s->s'转换的字符与字符串中位置为pos的字符匹配，则还有一个优势(s, pos) -> (s', pos + 1)。
建立图表后，你只需要检查一对(t, string.length())可达至少一个终端状态t（你可以使用任何图形遍历算法来检查它，比如深度优先搜索）。

来源

2017-04-16 22:26:10 kraskevich

如何检查我的线是否与NFA相符？

回答

相关问题