2
$\begingroup$

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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
4
$\begingroup$

The most significant difference is that Glushkov's NFA does not use $\epsilon$-transitions. Very roughly, the algorithm indexes the characters in the regular expression from left to right. Each state in the NFA is a subset of possible indices of the last character read from the input string.

Glushkov's construction [3] is described in detail in Aho, Sethi, and Ullman's classical compiler textbook, aka "The Dragon Book" [1]. The same construction was also described earlier by McNaughton and Yamada [4] and later by Berry and Sethi [2], so you may find it easier to search under those names.

  1. A. V. Aho, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley, 1988.

  2. G. Berry and R. Sethi. From regular expressions to deterministic automata. Theoretical Computer Science 48:117–126, 1986.

  3. V. M. Glushov. The abstract theory of automata. Russian Mathematical Surveys 16:1–53, 1961.

  4. R. McNaughton and H. Yamada. Regular expressions and state graphs for automata. IEEE Trans. Electronic Computers 9(1):39–47, 1960.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I see from the dragon book, and Mcnaughton,yamada paper that they are constructing DFAs directly from Regexes . I do not see any NFA's mentioned that specifically do not have ϵ-transitions. $\endgroup$
    – woodstok
    Commented Apr 30, 2013 at 14:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.