什么是glushkov NFA。Glushkov NFA和Thompson NFA有什么不同？

Question

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

什么是Glushkov NFA？它与由Thompson Construction创建的NFA有什么不同？

Answer 1

Flexible Pattern Matching in Strings包含了Glushkov自动机的一个非常好的定义。它是从regex解析树构造的NFA，使用last、first、follow和可为空的函数。此NFA不包含空的转换，这是与在Thompson构造中创建的NFA的主要区别。

Answer 2

我发现这篇文章包含了"A Unified Construction of the Glushkov, Follow, and Antimirov Automata"的Glushkov构造的定义。