Why is ε included as a step in NFA construction?

Question

Page 68 of Sipser's Intro to the Theory of Computation 3ed, shows the process to build an NFA. Why is ε included here? Can't you just go straight from a -> b?

Answer 1

You can, but it looks like the author is trying to strictly follow a certain set of rules for building an NFA from a regular expression. I don't have this book, but I suspect if you look back a page or two, you'll find a discussion and/or some diagrams of the rules being used. The rules don't always yield the most efficient construction, but they are enough for proving that regular expressions can always be converted to an NFA.

Answer 2

Using $\epsilon$-links, the constructions are easier to describe:

• In concatenation, you $\epsilon$-link every accepting state of the first to the initial state of the second factor (and deprive them of their accepting status)

• In union, you add a new initial state and $\epsilon$-link it to the initial states of every summand.

• In the star operator, you precede the whole with an accepting stated, $\epsilon$-linked to the old initial state, as well as add $\epsilon$-links from each old accepting state to the old initial state

One can get rid of the $\epsilon$ transitions, but if one desires to do so, it is perhaps easier to do this in a separate step. Sometimes, this is easy - for example, in the case you complain about: The first factor of the concatenation has a single accepting state and that state has no outgoing arrows. In that case, we can get rid of the $\epsilon$ by simply merging the two states; the result is the "just go straight" construction you had in mind. But what if the first factor were more complicated? E.g., if it had several accepting states? Or if it already had an outgoing arrow labelled $b$?