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

Well, I still don't understand the logic of using ε-transitions in the NFA, what's the real meaning? Skip state without performing a read?

For example, given the regex:

a*
  1. NFA:

    insert the description of the image here

  2. DFA:

    insert the description of the image here

Author: UzumakiArtanis, 2014-07-19

2 answers

Anthony's answer is perfect, but I was already writing so I will post because it can be of complementary help.

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

Like this:

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

  2. In the case of AFD (2), both states are of acceptance. So if the automaton receives an empty input, it terminates accepting it because it will be in state 0 (which is the initial one); otherwise, when reading the first symbol a, changes to state 1, where it no longer exits while reading symbols a from the input, eventually ending and accepting it after reading everything.

  3. In the case of AFN-ε (1), only state 3 is acceptance - with state 0 being the initial one. If the input is empty, it can be understood that eventually (at an arbitrary moment) the state of the automaton will change from 0 to 3 because there is a transition-epsilon linking these two states. And in that case, it will accept the empty input. However, the automaton can also change to state 1 arbitrarily, from where it will need to read at least one symbol a to move to state 2 (in this particular transition, deterministically), from where it can return to state 1 or move to State 3 also non-deterministically. Thus, it will only accept the input when it is empty, being that it has passed directly from state 0 to State 3; or when the input is not empty, being that it went from state 0 to state 1, from state 1 to state 2 at least once (being able to 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 computational 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 since it is always possible to convert an AFN-ε into an AFD (there is mathematical proof of this fact), any property tested on one is valid for the other.

Also Note that your examples assume that the Σ alphabet contains only the symbol a. If the input could also have the symbol b (for example, aaaabbab), the AFD itself would not be correct because it had no transition(ões) to the symbol b.

 6
Author: Luiz Vieira, 2014-07-19 12:43:35

Exactly. Epsilon transitions allow state change without consuming characters from the input string. This feature allied to the possibility of changing to more than one state at the same time characterize non-deterministic finite automata (actually a variation of the AFNDs according to Wikipedia article).

 5
Author: Anthony Accioly, 2014-07-19 02:02:44