# Transitions taking place in NFA

While studying about NFA and DFA in Compiler Design I couldn't get how they converted an regular expression to NFA as shown in NFA.I would like to know why there is an epsilon transition between (8 -> 10) and (9 -> 10).

Because I think even if we don't write states 9 and 10 the NFA would be unaffected. Can anyone tell me whether this is correct to do like that?

• What do you mean by "correct?" Commented Nov 20, 2014 at 5:37
• @RobertHarvey:That means I would like to know whether even if you remove states 9 and 10 whether this(change) would affect the NFA? Commented Nov 20, 2014 at 5:41
• FYI that NFA matches the regular expression (ab|c)* the DFA for that is pretty simple with only 2 states (plus a garbage state): a starting/accepting state with a c-loopback and a transition ato another state which has a transition b back. Commented Nov 20, 2014 at 8:47

Without states 9 and 10, we need a new start and accept state. Lets assume that these are states 7 for start (because there is an ε transition from 9 to 7) and 8 for accept (because there is an ε from 8 to 10).

However, this doesn't match the empty string anymore.

The diagram shown is the regular expression /^(ab|c)*$/. Without states 9 or 10 and the transition, the regular expression representing this NFA would be /^(ab|c)+$/ which is different.

• :Thanks for your answer.I understood the answer but whether we could make it into /^(ab|c)*\$/ by adding a transition (7 -> 8)? Commented Nov 20, 2014 at 5:52
• If you added an ε transition from 7->8, correct, states 9 and 10 wouldn't be necessary. Though note that you're now dealing more with conventions of writing NFAs. The depicted one is a bit more explicit about start and end states - probably the author's preference. DFAs have a canonical way to represent them, but NFA-ε are not so much because there are multiple ways to write the same NFA-ε. I personally am not overfly fond of this style of depiction - there are a lot of transitions that seem excessive; though thats the thing with instruction that they're trying to drill a specific point home.
– user40980
Commented Nov 20, 2014 at 6:19
• @justin I'd also suggest that you might want to look over at ComputerScience.SE. Programmers.SE tends to be more practical than theoretical (writing funny characters like ε makes us worry someone is going to stick them in an identifier at times). CS.SE is more focused on the theoretical than we are here and aren't afraid at throwing around greek characters and mathjax in the answers. You might want to look at the finite-automata tag there if you are after more in-depth answers.
– user40980
Commented Nov 20, 2014 at 6:23
• ... over here, you get crazy perl programmers who occasionally remember things they studied back in college.
– user40980
Commented Nov 20, 2014 at 6:24
• Another reason for this way of writing the NFA is that it allows for a completely mechanical transformation from a regex to an NFA that could even be performed by a machine with a minimum of rules. Commented Nov 20, 2014 at 7:44