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

For juxtaposition
(strings in L(r_{1}) followed by strings in L(r_{2}), 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.

Copyright © 1996 by David Matuszek

Last modified Feb 5, 1996