Back to the knowledge base

thompson construction

By dreamreal · 27 March 2026 · 121 lookups

Text

thompson construction is an algorithm for building an NFA from a regular expression using epsilon transitions to compose sub-automata. The most widely taught NFA construction, but requires epsilon-closure computation at every step.

URLs

https://en.wikipedia.org/wiki/Thompson%27s_construction

Tags

automata formal-languages compilers