Converting RE to NFA

Question

Which one is the correct way to show a RE union 0+1? I saw this two ways but I think both are correct. If both are correct why to complicate things?

Answer 1

They are both correct, as you stated.

The first one looks like it was generated using a set of standard rules -- in this case, it's overkill (and just looks silly), but in more complicated cases it's easier to follow easy rules than to hold the whole thing in your head and write an equivalent NFA from scratch.

In general, an NFA can be rewritten such that it has a single final state (obviously there's already only one start state).

Then, two NFAs in this form can be combined in such a way that the language they accept when combined is the union of the languages they accept individually -- this corresponds to the or (+) in a regular expression. To combine the NFAs in this way, simply create a new node to act as the start state and connect it with ε-transitions to the start states of the two NFAs.

Then, in order to neatly end the NFA in a single final state (so that we can use this NFA recursively for other unions if we want), we create an extra node to serve as the unified final state and ε-connect the old final states (which lose their final status) to it.

Using the general rules above, it's easy to arrive at the first diagram (two NFAs unioned together, the first matching 0, the other 1) -- the second is easy to arrive at via common sense since it's such a simple regex ;-)

Answer 2

The first construct belongs to the class of NFA with e-moves, which is an extension for the general NFA class. e-moves gives you an ability to make transitions without needing an input. For transition function, it is important to compute the set of states reachable from a given state using with e-transitions only. Obviously, adding e-moves does not allow NFA to accept non-regular languages so it is equivalent to NFAs and then DFAs in the end.

NFA with e-moves is used by Thompson's construction algorithm to build an automaton from any regular expression. It provides a standard way to construct an automaton from regexs when it's handy to automate construction.