For any x in , the regular expression x denotes the language {x}. This nfa represents exactly that language.

Note that if this were a dfa, we would have to include arcs for all the other elements of .

The regular
expression
denotes the language {},
that is, the language containing only the empty string.

The regular expression
denotes the language
; no strings belong
to this language, not even the empty string.

Since the final state is unreachable, why bother to have it at all? The answer is that it simplifies the construction if every nfa has exactly one start state and one final state. We could do without this final state, but we would have more special cases to consider, and it doesn't hurt anything to include it.

Copyright © 1996 by David Matuszek

Last modified Feb 5, 1996