glushkov

By dreamreal · 27 March 2026 · 178 lookups

Text: glushkov is an algorithm for building an epsilon-free NFA directly from a regular expression. Unlike Thompson's construction, every transition consumes a symbol, which simplifies downstream determinization into a DFA.
URLs: https://en.wikipedia.org/wiki/Glushkov%27s_construction
Tags: automata formal-languages compilers