1
$\begingroup$

Here I'm having some confusion on what exactly is the empty string $\epsilon$. I'm going to list some prerequisite definitions I have surrounding the string, so please correct them as necessary. I bolded what I felt were keys to understanding the empty string.

Other than that, these definitions (minus the parenthetical label) are verbatim from Introduction to the Theory of Computation by Michael Sipser.

(String) A string over an alphabet is a finite sequence of symbols from that alphabet.

(Alphabet) Any nonempty finite set.

(Finite Sequence) A sequence of objects is a list of these objects in some order.

(String Length) If $w$ is a string over $\Sigma$, the length of $w$, written $|w|$, is the number of symbols that it contains.

(Empty String) The string of length zero is called the empty string.

Note: Later on, for NFA's, Sipser defines their modified alphabet as some $\Sigma \cup \epsilon$.


Based on the above definitions, the empty string—being a string—is a sequence of symbols from an alphabet. Since it has length zero, it must be the empty sequence. Furthermore, since it has length zero, it must have zero symbols from any alphabet. Since it has no symbols from any alphabet it violates the definition of a string. Therefore, the empty string is not a string over any alphabet.

Note that Sipser's alphabet definition does not include the empty set.


I was informed by Robert Israel a few days ago that my logic above is wrong. I just don't see where.

Is the actual precise definition of empty string: the seqence of zero symbols from any nonempty alphabet? Are we taking as an axiom that we can take zero elements from a sequence? And if so, why does Sipser include the union of an alphabet with the empty string in his definition of NFA's? What is the difference between the empty string's relationship to an alphabet compared to it's role as member of a set like $\Sigma \cup \epsilon\, $?

$\endgroup$
  • $\begingroup$ The title asks about an empty string, but strewn throughout your post are references or mentions of the empty set. Are you conflating these two things? Do you feel that one of them is understood but the other one is not? You are correct in thinking of the empty string as a sequence of length zero. Since it has no entries, it may be identified as a string for any possible alphabet. $\endgroup$ – hardmath Feb 23 '19 at 20:42
  • $\begingroup$ Yes, I am possibly conflating the two. Hence the post. Sipser's definition of string states that is a sequence taken from an alphabet. I don't see how the zero sequence is taken from an alphabet. That's what I wrote in my last paragraph. $\endgroup$ – Zduff Feb 23 '19 at 20:49
  • $\begingroup$ Well, a set of things does not provide an order or an arrangement of the things that are contained in the set, only that those things, if any, are distinct (without repetitions). A string of things is a finite sequence or list, which does imply an order (sequencing) of things and also allows for repetitions to occur (by having the same thing in more than one position). So we should begin by clarifying the difference between a set and a string. $\endgroup$ – hardmath Feb 23 '19 at 20:53
  • $\begingroup$ Yes, I understand the difference between a set and a string. I'm not trying to be rude, and maybe my post was just unclear, but I clearly described what the empty string is, based on Sipser's definition, in my second block. It is the empty sequence. When I stated that "I am possibly conflating the two"—in reference to the empty set and the empty string—I meant that I am possibly conflating their properties not the fundamental difference between a set and a string. I do agree that's crucial, but I think it's clear from the context of my post that there's no confusion on that front. $\endgroup$ – Zduff Feb 23 '19 at 21:00
  • $\begingroup$ Are we taking as an axiom that we can generate an empty sequence from any set? $\endgroup$ – Zduff Feb 23 '19 at 21:02
2
$\begingroup$

Your mistake is a common one in mathematics, of thinking "an x of ys" has to contain at least one y, when what we really mean is it can't contain anything else. In other words, you thought the definition used an existential quantifier, but it actually uses a universal one. Let's try formalising this (without any MathJax, because quotation environments don't like it):

A: What is a string?

B: A function from a finite set to the preferred alphabet. (Sets of equal size are considered equivalent for this purpose, or you could say the string is an equivalence class of such functions.)

A: OK, but what's a function?

B: A set of ordered pairs (the first coordinate from the finite set of interest, the second from the alphabet) satisfying certain rules.

A: Oh, so the set has to have some ordered pairs in it?

B: No, it just needs to not have anything else.

"All" does not imply "some"; when there are no objects to be either examples or counterexamples, "all" is vacuously satisfied while "some" is violated. This may be surprising the first time you learn it, but in the long term it makes definitions, theorems etc. much easier, because you avoid a need to work around edge cases. (It also means you can get by with just one quantifier if you're prepared to negate all over the place, e.g. $\forall x\phi(x)$ means $\neg\exists x\neg\phi(x)$.) For example, there are $|\Sigma|^l$ length-$l$ strings on the above account for any non-negative integer $l$; $l=0$ isn't an exception.

$\endgroup$
  • 1
    $\begingroup$ So here, when we take a string as a sequence of symbols from an alphabet, this is more formally a universal quantifier? As in a string is a sequence of any symbols from an alphabet. If there are no symbols taken from such an alphabet, the string definition is vacuously satisfied? $\endgroup$ – Zduff Feb 24 '19 at 2:54
  • $\begingroup$ The quantifier comes from saying all sequence elements are symbols from that alphabet. The empty sequence is "a sequence of" any sort of mathematical object. $\endgroup$ – J.G. Feb 24 '19 at 7:08
1
$\begingroup$

The definitions look sound. Here are some aspects which might help to clarify the situation.

(String) A string over an alphabet is a finite sequence of symbols from that alphabet.

  • A finite sequence is a sequence of zero or more symbols from the alphabet $\Sigma$. The definition of a String does not explicitly exclude the empty string.

(Finite Sequence) A sequence of objects is a list of these objects in some order.

  • Again, the empty list of objects is not explicitly excluded, allowing the finite sequence also to be the empty sequence.

(Empty String) The string of length zero is called the empty string.

  • We can consider the alphabet $\Sigma$ which contains all symbols as containing all strings of length one. Additionally to the symbols of $\Sigma$ a new notation empty string is introduced addressing the special case of a sequence with length zero.

  • Note, the definition uses the formulation The string of length zero and not A string of length zero indicating there's one and only one instance of an empty string and also indicating a kind of universality, that the empty string can be used in connection with any alphabet $\Sigma$.

An example: $\Sigma:=\{a,b\}$. We can list the valid strings built from $\Sigma$ with respect to the length of the strings. We have \begin{align*} \Sigma^0&=\{\varepsilon\}\\ \Sigma^1&=\{a,b\}\\ \Sigma^2&=\{aa,ab,ba,bb\}\\ &\vdots\\ \Sigma^{+}&=\{a,b,aa,ab,ba,bb,aaa,\ldots\}\\ \Sigma^{\star}&=\{\varepsilon,a,b,aa,ab,ba,bb,aaa,\ldots\}\\ \end{align*}

We see with the notation above $\Sigma \cup \{\varepsilon\}=\Sigma^1\cup\Sigma^0$.

$\endgroup$
0
$\begingroup$

The situation with alphabets and strings is very similar to the situation with sets and collections of subsets. The only difference is that the elements of a subset are not ordered and appear at most once. In a string the order of elements matters and an element can appear more than once. The empty string is exactly similar to the empty string. Notice that the empty set is a subset of any given set, and similarly the empty string is a string of any given alphabet. In fact, the empty string is the only string of the empty alphabet, if the empty alphabet is not excluded.

An equivalent formulation of alphabets and strings is a free monoid on a set of free generators. The generators are the alphabet and the strings are elements of the free monoid. The empty string is now the identity element of the monoid. However, by using the free semigroup instead, the only difference is that there is no identity element in the free semigroup. The choice to allow an identity element is mostly one of convenience. However, a slight ambiguity is that the identity elements of different free monoids all look the same. That is, the empty set is uniquely defined by its property that it has no elements. But, the identity elements of each monoid are not identical even though they have the same property of being the identity element for its monoid. Perhaps it would be clearer to distinguish each empty string with its associated alphabet, but this is not done.

Your question about NFA and modified alphabet is just a common convention. The extra element could be any element that is not in the alphabet originally. It is a cause for confusion, but it is convenient to use the empty string because it can never be an alphabet element. Bt the way, a more accurate notation would be $\,\Sigma \cup \{\epsilon\}\,$ to denote the union of two sets. In this case, the set of letters in an alphabet and a singleton set containing only the sempty string.

$\endgroup$
0
$\begingroup$

Well, given the alphabet $A$ and an integer $n\geq 0$. The collection of mappings $f:[n]\rightarrow A$ correspond one-to-one with the collection of words/strings of length $n$ over $A$. The correspondence is given by sending the mapping $$f=\left(\begin{array}{ccc} 1 & \ldots & n\\ a_1 &\ldots & a_n\end{array}\right)$$ to the word (sequence of images without delimiters) $$w_f = a_1\ldots a_n.$$ For $n=0$, the empty mapping corresponds to the empty word.

$\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.