What is the real meaning of using ε-transitions in NFA?

Question

Well, I still don’t understand the logic of using ε-transitions in NFA, what is the real meaning? Jump from state without making a reading?

For example, given the regex:

a*

1. NFA:

   

2. DFA:

   

Answer 1

Anthony’s answer is perfect, but I was already writing so I’ll post it because it might be complementary help.

The two automata (1) and (2) are equivalent. The difference well explained by Anthony is that the Epsilon (or Lambda) transitions allow changing states without consuming characters, working almost as if the automaton changes state "alone" (the "nondeterministic" in the name comes precisely from the fact that changes can occur arbitrarily, and not only to a single well-defined state for each symbol, as in the DFA).

Thus:

1. the regular expression a* must accept only an empty entry (no symbol) or an entry with one or more symbols a (for example, a, aa, aaa, ...).

2. in the case of DFA (2), both states are accepted. Then, if the automaton receives an empty input, it closes by accepting it because it will be in state 0 (which is the initial); otherwise, by reading the first symbol a, changes to state 1, from which it no longer leaves while reading symbols a of the entrance, eventually ending and accepting it after reading all.

3. in the case of AFN-ε (1), only state 3 is accepted - where state 0 is initial. If the input is empty, it can be understood that eventually (at an arbitrary time) the state of the automaton will be changed from 0 to 3 because there is an Epsilon transition connecting these two states. And in that case, he’ll accept the empty entrance. However, the automaton can also switch to state 1 arbitrarily, from where you need to read at least one symbol a to go to state 2 (in this particular transition, deterministically), from where you can go back to state 1 or to state 3 also in a non-deterministic way. Thus, he will only accept the entry when it is empty, and he has passed directly from state 0 to state 3; or when the entry is not empty, and he has passed from state 0 to state 1, from state 1 to state 2 for once (can circulate between states 2, 1 and 2 again for each new symbol read), and finally from state 2 to state 3.

Note that these automata are only conceptual models of computing machines processing a symbolic input, and the idea of using an AFN-ε is because certain problems are more easily described (using fewer states as well) in this way. But as it is always possible to convert an AFN-ε into an AFD (there are mathematical proofs of this fact), any property tested on one is valid for the other.

Note also that your examples assume that the alphabet Σ contains only the symbol a. If the entrance could also have the symbol b (for example, aaaabbab), the DFA itself would not be correct for not having transition(s) to the symbol b.

Answer 2

Exactly. Transitions Epsilon allow state change without consuming input string characters. This feature coupled with the possibility of changing to more than one state at the same time characterizes nondeterministic finite automata (actually a variation of the Afnds according to Wikipedia article).