[Overview] [Previous] [Next]

From Primitive Regular Expressions to NFAs

Every nfa we construct will have a single start state and a single final state. We will build more complex nfas out of simpler nfas, each with a single start state and a single final state. The simplest nfas will be those for the primitive regular expressions.

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.