格鲁什科夫 NFA 是什么。格鲁什科夫 NFA 和汤普森 NFA 有什么区别？

Question

我在http://lambda-the-ultimate.org/node/2064看到了这个术语“Glushkov NFA”。搜索引擎返回对使用 glushkov nfa 的文章的引用，但没有关于 glushkov nfa 本身的具体信息。

什么是格卢什科夫 NFA？它与 Thompson Construction 创建的 NFA 有什么不同？

Answer 1

字符串中的灵活模式匹配包含格卢什科夫自动机的非常好的定义。它是使用 last、first、follow、nullable 函数从正则表达式解析树构建的 NFA。该 NFA 不包含空转换，这是与 Thompson Construction 创建的 NFA 的主要区别。