0

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?

NFA

J. Doe
  • 405

2 Answers2

0

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.

Ted
  • 33,788
  • There's this rule: R 。ε = R, Joining the empty string to any string will not change it. Are they trying to prove this point? I find including ε in the NFA construction rather pointless. – J. Doe Nov 07 '19 at 07:08
  • Sipser is showing an example of an algorithm that works for any regular language. When you concatenate two languages L and R, you take the (recursively built) NFAs and attach the accepting states of L to the initial states of R by epsilon transitions. Note that this is exactly what Sipser does for this language. You are correct that in this special case there is a more efficient approach. In general, however, you will need these epsilon transitions. – HallaSurvivor Nov 07 '19 at 07:17
  • @HallaSurvivor, are you saying the epsilon transitions are used to mark concatenations? – J. Doe Nov 07 '19 at 07:37
  • And other things too. For instance, if L accepts a language l, then attaching all the accepting states of L to the initial ones with epsilon transitions will give a machine accepting l* – HallaSurvivor Nov 07 '19 at 16:23
0

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$?

Hagen von Eitzen
  • 374,180