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

Question

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

Navigation

#1 by (6 votes)
#2 by (5 votes)

5

Well, I still do not understand the logic of using ε-transitions in the NFA, what's the real meaning? Skip status without reading?

For example, given the regex:

a*

NFA:

DFA:

asked by anonymous 19.07.2014 / 02:58

2 answers

5

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

19.07.2014 / 03:54

Generate unique color for each result Yield return within a using

score 6 · Accepted Answer

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

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

So:

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

In the case of AFD (2), both states are accepted. Then, if the automaton receives an empty input, it ends up accepting it because it will be in state 0 (which is the initial); otherwise, when reading the first symbol a , it changes to state 1, where it does not go any further while reading symbols a of the entry, eventually ending and accepting it when finished reading everything.

In the case of AFN-ε (1), only state 3 is accepted - state 0 being the initial state. If the input is empty, one can understand that eventually (at an arbitrary moment) the state of the automaton will be changed from 0 to 3 because there is an epsilon transition linking these two states. And in that case, he will accept the empty entry. However, the automaton can also switch to state 1 arbitrarily, from where it will need to read at least one a symbol to go to state 2 (in this particular deterministic transition), from where it can return to state 1 or to proceed to state 3 also in a non-deterministic manner. Thus, it will only accept the input when it is empty, being that it passed directly from state 0 to state 3; or when the input is not empty, it has gone from state 0 to state 1, from state 1 to state 2 at least once (being able to move 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 just conceptual models of computational machines that process 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 in one is valid for the other.

Note also that their examples assume that the alphabet Σ contains only the symbol a . If the entry could also have the symbol b (eg aaaabbab ), the AFD itself would not be correct because it did not have transition (s) to the b symbol.