2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $\varepsilon$ is a label given to some of the transitions, it is unrelated to the input string. Read the formal definition in full, the wikipedia article you link does a good job at explaining it. $\endgroup$ – quicksort Feb 8 '17 at 21:11
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Note however that in the definition of push-down automata $\epsilon$ transitions are also used. However there the construction of closure is more complicated, as for PDA also the stack changes, and the closure may yield an infinite set of state-stack pairs. For me it is more helpful to see $\epsilon$-moves as instructions that do not consume input. $\endgroup$ – Hendrik Jan Feb 9 '17 at 11:17
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thx for input, but you haven't answered any of my questions. $\endgroup$ – Dennis Grinch Feb 8 '17 at 21:28
  • $\begingroup$ I've edited my response, hopefully that gives you a better picture. $\endgroup$ – JustAnotherSoul Feb 8 '17 at 22:24
  • $\begingroup$ "it can 'explore' two plausible" I think possibly more than two. $\endgroup$ – Evil Feb 9 '17 at 0:23
  • $\begingroup$ Yes. It is possibly more than two. $\endgroup$ – JustAnotherSoul Feb 9 '17 at 19:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.