[Syllabus] [Previous] [Next]

From Regular Expressions to NFAs

We will build more complex nfas out of simpler nfas, each with a single start state and a single final state. Since we have nfas for primitive regular expressions, we need to compose them for the operations of grouping, juxtaposition, union, and Kleene star (*).

For grouping (parentheses), we don't really need to do anything. The nfa that represents the regular expression (r1) is the same as the nfa that represents r1.

For juxtaposition (strings in L(r1) followed by strings in L(r2), we simply chain the nfas together, as shown. The initial and final states of the original nfas (boxed) stop being initial and final states; we include new initial and final states. (We could make do with fewer states and fewer empty string transitions here, but we aren't trying for the best construction; we're just trying to show that a construction is possible.)

The + denotes "or" in a regular expression, so it makes sense that we would use an nfa with a choice of paths. (This is one of the reasons that it's easier to build an nfa than a dfa.)

The star denotes zero or more applications of the regular expression, so we need to set up a loop in the nfa. We can do this with a backward-pointing empty string arc. Since we might want to traverse the regular expression zero times (thus matching the null string), we also need a forward-pointing empty string arc to bypass the nfa entirely.

Copyright 1996 by David Matuszek
Last modified Feb 5, 1996