thompson construction

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, compiler

Sign in to change this factoid.