python - 我如何检查我的线路是否与 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

1. 您可以将自动机转换为 DFA(之后检查变得微不足道)。这种方法在 NFA 很小但要测试的字符串数量相当大的情况下很有用。

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