[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 (r₁) is the same as the nfa that represents r₁.

For juxtaposition (strings in L(r₁) followed by strings in L(r₂), 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 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 arc. Since we might want to traverse the regular expression zero times (thus matching the null string), we also need a forward-pointing arc to bypass the nfa entirely.