what is glushkov NFA. What is the difference between Glushkov NFA and Thompson NFA?

Question

I saw this term "Glushkov NFA" at http://lambda-the-ultimate.org/node/2064 . Search engines are returning references to articles that use glushkov nfa, but nothing specific about the glushkov nfa itself.

What is Glushkov NFA? How different is it from the NFA created from Thompson Construction?

Answer 1

Flexible Pattern Matching in Strings contains a very good definition of Glushkov automata. It is the NFA constructed from a regex parse tree using the last,first, follow,nullable functions. This NFA does not contain empty transitions which is the main difference from the NFA created in Thompson Construction.

Answer 2

I found this article "A Unified Construction of the Glushkov, Follow, and Antimirov Automata" containing a definition of the Glushkov construction of an NFA.