thompson construction

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.
automata, formal languages, compiler

Sign in to change this factoid.