Meaning of ε in NFA-ε?

Question

In wikipedia NFA-ε transition function defined as follows $Δ : Q × (Σ ∪ \{ε\}) → P(Q)$, where $Σ$ is an alphabet and $ε$ - empty string. I don't understand the meaning of $ε$ in this context.

Assuming $ε$ means a sequence of symbols with length of zero, as per definition.

Alphabet $Σ$ is a set of symbols. But symbol $\neq$ sequence of symbols (string). Thus, $(Σ ∪ \{ε\})$ is no longer set of symbols, but a mixed set. I don't know much of set theory, but is this mixed set allowed in this context?

Also. When does NFA ε-transition happen?

1. ε-transition happens when input symbol is an empty string? Meaning, that presence of empty string is necessary condition for ε-transition .
2. ε-transition happens when there are no input symbol at all? Meaning, that presence of empty string is not necessary condition for ε-transition.

I think that the latter case, or I am wrong?

I would have avoided this confusion, if $ε$ would mean "NO_INPUT" symbol, rather an empty string as per definition.

Answer 1

I don't know much of set theory, but is this mixed set allowed in this context?

There's an axiom of set theory that, for any two sets $A,B$ then $A \cup B$ is also a set. So it's definitely defined.

When does NFA ε-transition happen?

Try not to think of NFAs as actual machines, but instead focus on their mathematical definitions.

For every state $q$ of our NFA, there is some set $\epsilon CLOSE(q)$ of sets reachable from $q$ using 0 or more $\epsilon$-labelled transitions.

In an NFA without $\epsilon$-transitions, from a state $q$ and an input letter $a$, then the transition function $\delta(q,a)$ gives a set of states reachable from $q$ on input $a$, specifically all those states with an $a$-transition from $q$.

In an $\epsilon$-NFA, the states you can reach from $q$ on input $a$ is defined as to be $\{q' \mid (q,q'') \in \delta, q' \in \epsilon CLOSE(q) \}$. That is, it's the set of states you can get by following $a$.

The exact definitions are a bit more complicated, because you have to account for also taking $\epsilon$-transitions from whatever state you're starting at.

A word is accepted by an NFA if there's some sequence of transitions you can take to an accepting state where, when you concatenate the labels of all the transitions you take (treating the character inputs as 1-letter words), you get that word.

The point is, the meaning is just this definition. There's no "when" it happens, because it's sets and functions and relations all the way down.

I would have avoided this confusion, if ε would mean "NO_INPUT" symbol, rather an empty string as per definition.

We usually don't say this, because $\epsilon$ doesn't occur in the input words. (There's an infinite number of $\epsilon$s implicitly between every character of the words, but then our representation isn't unique we don't want that.) What you could do is have some special symbol which, when attached to a transition, denotes that it's a transition that can be taken without consuming input. But that's purely a definition of style: the final result is not changed.

Answer 2

An epsilon transition is simply a transition that doesn't consume any characters in the input string.

Taking it is optional, and it is what makes the non-deterministic finite automata non-deterministic: by allowing it to 'branch' it can 'explore' two plausible paths through the language it accepts. It is essentially just a space saving measure: DFAs (which do not permit epsilon transitions) are computationally equivalent to NFAs. There are steps to convert an NFA to an equivalent DFA, removing epsilon transitions is part of this conversion.

To explicitly draw out answers to your questions: In your example it is akin to a 'NO_INPUT' symbol, but more like 'NO_COST'. Think of it like this: Each edge has a 'cost' in the symbol along it that you must pay to transition along that edge. An epsilon has no cost. You don't 'spend' any characters from your input string to traverse that edge. Because of that, you now have multiple paths: Take the epsilon transition (or transitions) and spend no symbols from the input string, or 'spend' an input string along an edge. So it essentially the computation 'branches', and your NFA accepts a string if any path through it concludes in a success state.