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（您可以使用任何图遍历算法来检查它，例如深度优先搜索）。