我制作了由正则表达式 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
最佳答案
您可以将自动机转换为 DFA(之后检查变得微不足道)。这种方法在 NFA 很小但要测试的字符串数量相当大的情况下很有用。
您还可以构建一个新图,其中每个顶点都是对(NFA 的状态,字符串中的位置)。如果它是 epsilon 转换,则每个位置的状态和另一个状态之间都有一条边。还有一条边
(s, pos) -> (s', pos + 1)
如果自动机中s->s'
转换的字符匹配字符在字符串中的pos
位置。
构建图形后,您只需要检查一对(t, string.length())
是否可以到达至少一个终端状态t
(您可以使用任何图遍历算法来检查它,例如深度优先搜索)。
关于python - 我如何检查我的线路是否与 NFA 匹配?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43440840/