1
$\begingroup$

I'm wondering if this visualization makes sense with the definition of the empty string ε. I suppose it does because it doesn't seem to contradict its definition (ε is a string with no characters).

If that's the case, in finite state machines with empty transitions, is it always possible to assume ε is "before" the character a that should be read next, and take the empty transition instead?

If the next state also has an empty transition to another state, can I assume ε is "before" a again, even though the automata had just "consumed" ε in the last operation? In other words, can I assume there is an indefinite number of empty strings between any two characters in a string in a regular language?

$\endgroup$
  • $\begingroup$ The empty string consists of no characters. It is not an object. It is the absence of an object. Two absences are no more nor less absent than a single absence; indeed, it is impossible to count how many absences there are before two presences. $\endgroup$ – rici Jan 21 '17 at 5:50
4
$\begingroup$

The empty string is not there between every two characters implicitly but quite explicitly. In fact, there are two empty strings between any two characters, and between those two empty strings there is another, third, empty string. However, since empty strings are empty, them being there is like them not being there at all.

Let's consider this situation from a slightly more general point of view, but without using fancy words. In a sum $1 + 2$ is there a zero in between? Yes, since obviously $1 + 0 + 2 = 1 + 2$, and in fact also $0 + 0 + 1 + 0 + 0 + 0 + 2 + 0 = 1 + 2$, so that's a whole lot of zeroes. Is this sort of thinking useful? Well, in certain situations it is, for instance when we perform algebraic manipulations of numbers.

It might help to write strings as finite lists, i.e., instead of aabab we write $[a, a, b, a, b]$. With this notation the empty string is just $[]$, which is probably less confusing than the Greek letter $\varepsilon$. Concatenation then is actually concatenation (link together in a chain or series, according to my dictionary): $$[a, a, b][b, a] = [a, a, b, b, a].$$ And now, it makes perfect sense to say that there are empty strings everywhere, like ghosts: $$[a, a, b][][b, a] = [a, a, b, b, a] = [a, a, b][b, a].$$ Finite automata with silent transitions do not "consume $\varepsilon$". A silent transition happens when no symbol is consumed. You might think that "to consume no symbol" is the same as "to consume the empty string" but that is not so! An automaton (at least of the ordinary kind) consumes one symbol when it makes a transition, or it does not consume anything at all. An empty string is not a symbol, and therefore it cannot be consumed during the transition of an automaton.

More formally, the transition function $\delta$ has the type $S \times \Sigma \to \Sigma$, where $S$ is the set of states and $\Sigma$ is the alphabet. The empty string has type $\Sigma^*$ and so it cannot be an argument to $\delta$. The types don't fit.

$\endgroup$
  • $\begingroup$ A concise, comprehensive and well formatted answer. Thank you Andrej. +1 P.S: I'm stealing your quote " it makes perfect sense to say that there are empty strings everywhere, like ghosts" $\endgroup$ – P. Soutzikevich Feb 20 at 15:43
2
$\begingroup$

You may see the finite-length strings of an alphabet $\Sigma$ as the free monoid generated by $\Sigma$ with respect to composition, with $\varepsilon$ as the identity. Therefore, although it is not in general particularly useful, since by definition of identity $\varepsilon \circ A = A = A \circ \varepsilon$, you may certainly introduce any number of $\varepsilon$ in any position, without changing the original string.

However, bear in mind that the definition of a $\varepsilon-$NFA doesn't involve a "current state" but a rather a set of current states, I'm not sure your alternative definition would work as stated.

$\endgroup$

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.