# Importance of the empty string

In the sense of a string distinct from a null reference string, what is the importance of an empty string in CS (and specially in formal languages)?

Why do you need a separate concept, that of 'empty string', which even has it's own Greek letter (ε)?

Couldn't just an EOL character replace it?

• What makes you think that there is only one "correct" definition for the concept? – Raphael Jan 5 '14 at 17:05
• @Raphael: what makes you think that I think that? – Quora Feans Jan 5 '14 at 17:43
• I was reading between the lines. A better comment may have been: have you tried defining formal languages that way and proving some basic theorems? – Raphael Jan 5 '14 at 19:53
• What do you mean by "null reference string"? Is that a programming language concept ? What do you mean by a "separate concept" ? Separate from what ? What difference do you make between the greek character ε and the EOL character, except for the fact that they have different uses in the representation of texts? Finally, what do you mean by "need", as we can often do without specific concepts or notations, and get things done? Do we need high level programming languages? Well, they make programming easier in many ways, but are not Undispensable. You also seem to confuse syntax and semantics. – babou Jan 8 '14 at 9:07
• Null reference string: would be a string variable pointing to a null (that means non existing value). Separate concept: you don't have a term for a string of length 44, but you bother to give a string of the length 0 a name. Following the same line of thought, it has to be important, otherwise you wouldn't give it a term, nor a Greek letter, unless you planned to use it repeatedly. Regarding EOL: if EOL could cover all functions that the ε has, then the latter would be redundant. – Quora Feans Jan 8 '14 at 14:41

There is a mathematical meaning for the empty string. Indeed the concatenation product of words is an associative operation. But this operation also has a neutral element, namely the empty word. For this reason, the empty word is also frequently denoted by $1$, which allows one to write, for each word $u$, $$1 \cdot u = u = u \cdot 1$$

Of course, if the alphabet is $\{0, 1\}$, it is not a good idea to denote the empty word by $1$ and this is probably the reason why the notation $\varepsilon$ (or sometimes $\lambda$) was introduced. But as Yuval Filmus pointed out, the empty word is a word of length $0$, that is, it contains no letter.

It is certainly disturbing to denote the empty word by $1$ (or by a greek letter $\varepsilon$ or $\lambda$), but you have to take it as a conventional notation, in the same way you denote the empty set by $\emptyset$.

• It's worth noting that $(\Sigma^*, \cdot)$ is a monoid. Investigating algebraic properties of formal languages can yield interesting results, e.g. semiring parsing. – Raphael Jan 5 '14 at 17:09

The empty string is like zero. It represents "nothing" but is a fundamental concept. As a very simple example, a word $a$ is a prefix of a word $b$ if $b = aw$ for some word $w$. If you don't allow the empty string, a word wouldn't be a prefix of itself.

The EOL character is a character in a specific character set. If we're interested in strings over $\{0,1\}$, we have no EOL. Additionally, EOL is a character, so a string consisting of EOL is not empty.

• Whether a word is a prefix of itself is a matter of definition. If you decide not to consider the empty string, you have to change some definitions accordingly to enable a consistent variant of the theory of strings. - - The character EOL can indeed represent the empty string. Representations can use any appropriately structured device. I can use the characters z,e,r,o, and n to represent strings over $\{0,1\}$, for example with "onezeroone" to represent what is usually noted "101" and "none" for the empty string. Not that I recommand it. – babou Jan 8 '14 at 23:23
• You can do whatever you want, but some definitions are "better" than others. And there are reasons. I'm giving one such reason. – Yuval Filmus Jan 8 '14 at 23:27
• Not sure which point you are answering. It seems to be only the first. If you are not allowing the empty string, your definition of prefix is most probably inadequate. Or can you give a reason why it should be better? The real reason you should give to justify that the empty string is fundamental is that it is harder (but most likely possible) to develop the theory without it. For example you have to give a more complex definition of what it means for a string to be a prefix of another. It is a more subtle point. Think of the Greeks doing arithmetics without zero. – babou Jan 9 '14 at 0:12
• You can also justify the usual definition of prefix vs. yours, which is usually called proper prefix. But your example regarding zero gives it all - life is so much easier with it. – Yuval Filmus Jan 9 '14 at 0:16
• If the empty string is not allowed, my definition of proper prefix is the usual definition of prefix (when empty string is allowed), and my definition of prefix is that u is a prefix of v iff u is a proper prefix of v or equal to v. The point is to remain semantically consistent with the theory that allows for the empty string. Yes, life is easier with the empty string ... but things are not different without it in the way you seemed to imply in your remark about a word no longer being a prefix of itself. I think it is an important point. – babou Jan 9 '14 at 0:54

Using an end-of-line (EOL) character is equivalent in terms of expressive power – anything you can do with the empty word $\varepsilon$, you could redefine to do with EOL instead – but using it would be a monumental pain in the butt. The conventional definitions are:

An alphabet is a finite set $\Sigma$ of symbols. A string $s$ over the alphabet $\Sigma$ is a finite sequence $s_1\dots s_\ell$, where each $s_i\in\Sigma$. We write $|s|$ for the length of $s$, with $|s_1\dots s_\ell|=\ell$; the unique word of length zero is denoted $\varepsilon$. A substring of $s_1\dots s_\ell$ is any string $s_i\dots s_j$, where $1\leq i\leq j\leq \ell$. The concatenation of strings $s_1\dots s_\ell$ and $t_1\dots t_m$ is the string $s_1\dots s_\ell t_1\dots t_m$ of length $\ell+m$.

Compare this with:

Let $\dashv$ be a distinguished end of line symbol. An alphabet is a finite set $\Sigma$ of symbols such that ${\dashv}\in\Sigma$. A string $s$ over the alphabet $\Sigma$ is a finite sequence $s_1\dots s_\ell$ where $s_i\in\Sigma\setminus\{{\dashv}\}$ for $i<\ell$ and $s_\ell={\dashv}$. We write $|s|$ for the length of $s$, with $|s_1\dots s_\ell|=\ell-1$. A substring of $s_1\dots s_\ell$ is any string $s_i\dots s_j{\dashv}$, where $1\leq i\leq j< \ell$. The concatenation of strings $s_1\dots s_\ell$ and $t_1\dots t_m$ is the string $s_1\dots s_{\ell-1} t_1\dots t_m$ of length $\ell+m-2$.

Note the extra fiddliness and the potential for off-by-one errors, especially in the definition of concatenation. Also, consider defining automata over these terminated strings. In addition to checking whether its input has whatever properties the language requires, any automaton must now check that the last character of the input is ${\dashv}$, which will (I think) add two states to every automaton.

The empty string $\varepsilon$ has the same role as zero does in the natural numbers. It's the identity for the most basic operation (concatenation for strings, addition for naturals). This is important if you want to build any kind of algebraic structure, such as groups or monoids, which gives access to a large area of potentially useful mathematical results. More straightforwardly, it makes a great base-case for inductions, since the hypothesis is often trivial for the empty string. Indeed, when you do induction on strings, you're implicitly using the following inductive definition of $\Sigma$-strings:

• $\varepsilon$ is a $\Sigma$-string;
• if $s$ is a $\Sigma$-string and $\sigma\in\Sigma$, then $s\sigma$ is a $\Sigma$-string.

That also becomes more fiddly with terminated strings:

• ${\dashv}$ is a $\Sigma$-string;
• if $s{\dashv}$ is a $\Sigma$-string and $\sigma\in\Sigma\setminus\{{\dashv}\}$, then $s\sigma{\dashv}$ is a $\Sigma$-string.

Of course, you could do it the other way round and say that if $s$ is a string, then so is $\sigma s$. At that point, there's little to choose between terminated and unterminated strings but your induction might be better suited to adding characters on the end than the beginning.

Terminated strings are fine for programming with but they're not well suited to mathematics. When you're programming, you need some way of knowing when the string $s_1\dots s_\ell$ ends; when you're doing mathematics, it's obvious that $s_\ell$ is the last character from the way the string is written.

I've just noticed that you ask about the difference between a null reference and the empty string. A null reference is no string at all; the empty string is a string but it has no characters on it. If you like, it's the difference between having a blank piece of paper (empty string) and having no paper at all (null reference).

• IMO, the first part of your answer is misguided. The conventional definition aims at defining abstractedly what a string is, independently of how it is represented. The second definition is a formal way to define one possible notation for it, but is nothing you want for reasoning about strings. You are reinforcing a confusion between syntax and semantics suggested by the somewhat awkward question of the OP. The rest of your answer suffers the same problem. – babou Jan 8 '14 at 23:28
• In your last paragraph, you repeat the confusion between syntax and semantics. Empty string is an abstract concept, and it could well be represented in the conputer by a null reference, while non-empty strings are represented by whatever is deemed convenient. The only requirement is that string manipulation functions are written accordingly so that the mathematical semantics of strings is adequately respected. Note that paper too is only for representing strings. Abstract mathematical entities are not of this world. – babou Jan 8 '14 at 23:29
• @babou As I stated ("anything you can do with the empty word $\varepsilon$, you could do with EOL instead"), the two options are semantically equivalent and I discuss what this semantic role is (e.g., the identity for the concatenation operator). Separately, I discuss how EOL is syntactically inconvenient. In what way is this confusing syntax with semantics? – David Richerby Jan 8 '14 at 23:39
• The first definition is a standard one for the abstract concept. It does not (have to) say anything about the way string are actually represented. The OP is concerned with representation, and, in the second definition, you are mimicking a proposed representation as if it were the abstract definition of the concept, which is of course more awkward. Symbol $\dashv$ should not be in $\Sigma$, but only be a notational device used to terminate string representations (possibly a very minor inconvenience) so that the notation is uniform for the empty string. You did confuse syntax and semantics. – babou Jan 9 '14 at 2:05
• As I said, your statement about the syntactic inconvenience of EOL is unwarranted. You created the problems by using an inadequate definition (your second definition for strings). In my (rewritten) answer, towards the end, I give the definition you should have been using, which shows that these problems do not exist. The ⊣ must be part of the notation, not a symbol in the represented string. – babou Jan 9 '14 at 22:53

Short answer: the empty set (i.e. the set of strings which contains no strings) is like zero, but the empty string (i.e. the set of strings which contains one zero-length string) is like one.

One way to axiomatise formal languages is as an idempotent semiring. A semiring is a structure with two binary operations $+$ and $\cdot$, and two distinguished elements $0$ and $1$, and obeys the following axioms. First off, $+$ is a commutative monoid with identity $0$:

$$(A + B) + C = A + (B + C)$$ $$0 + A = A + 0 = A$$ $$A + B = B + A$$

Secondly, $\cdot$ is a monoid with identity $1$: $$(A\cdot B)\cdot C = A\cdot(B\cdot C)$$ $$1\cdot A = A\cdot 1 = A$$ Multiplication left and right distributes over addition: $$A\cdot (B + C) = (A\cdot B) + (A\cdot C)$$ $$(A + B)\cdot C = (A\cdot C) + (B\cdot C)$$ Multiplication by 0 annihilates: $$0\cdot A = A\cdot 0 = 0$$ and finally, addition is idempotent: $$A + A = A$$

"Addition" can be interpreted as set union and "multiplication" can be interpreted as string concatenation.

Oh, and the link goes very deep. The Kleene closure operator, which is intuitively defined as:

$$A^* = 1 + A + A^2 + A^3 + \cdots$$

behaves like exponentiation. Think of the power series of $e^x$, plus the fact that addition is idempotent.

Terminal characters behave like variables. In particular, we can define evaluation at zero:

$$a(0) = 0$$ $$(AB)(0) = A(0) B(0)$$ $$(A+B)(0) = A(0) + B(0)$$ $$A^*(0) = 1$$

Given a regular expression $E$, $E(0)$ is either $0$ or $1$. It is $1$ if the empty string is a member of $E$, and $0$ otherwise.

We can also define a derivative, called the Brzozowski derivative:

$$\frac{\partial a}{\partial a} = 1$$ $$\frac{\partial b}{\partial a} = 0$$ $$\frac{\partial (A+B)}{\partial a} = \frac{\partial A}{\partial a} + \frac{\partial B}{\partial a}$$ $$\frac{\partial AB}{\partial a} = A(0) \frac{\partial B}{\partial a} + \frac{\partial A}{\partial a} B$$ $$\frac{\partial A^*}{\partial a} = \frac{\partial A}{\partial a} A^*$$

The only odd rule here is the one for multiplication. It's almost like the familiar product rule; the difference is due to the fact that concatenation is non-commutative.

What the derivative intuitively means is that $\frac{\partial E}{\partial a}$ is the set of strings in $E$ which start with the symbol $a$, but with that $a$ removed. So $a \frac{\partial E}{\partial a}$ is the set of strings in $E$ which start with $a$.

Thinking about it for a moment, if ${a\ldots z}$ is the alphabet, then:

$$E = E(0) + a \frac{\partial E}{\partial a} + b \frac{\partial E}{\partial b} + \cdots + z \frac{\partial E}{\partial z}$$

This is Taylor's theorem, only for regular languages. Moreover, it is also a rule for creating DFAs directly from regular expressions! $E(0)$ is $1$ if and only if the initial state is a final state, and the other terms are the transitions.

One remarkable thing about this is that the familiar regular expression operators (plus some less familiar ones, such as set intersection and set difference) are completely determined by their derivatives, plus their evaluation at zero. This is what we'd expect from the fundamental theorem of calculus, but it's interesting to see it here too.

Incidentally, this theory scales up to context-free and recursive languages too, but you need a bit more machinery for that which I won't go into here.

# A fundamental question about mathematics

This answer was reorganized after the OP gave more precisions as to the meaning and intent of his question. I also comment other answers here, as it is awkward to do so in the usual comment format. Commenting them also gives extra insight into the relevant issues.

## In a nutshell

Your intuition is quite correct that the empty string plays a special role in the study of strings and formal languages, and that is the reason why it is often given a special name or notation. Strings over a given set of symbols form an algebraic structure called a monoid, with the concatenation operation which has a neutral element: the empty string. See the answer by J.-E. Pin.

You are also correct that there could be many other notations or representation for it. The choice of representation is dictated by convenience, perspicuity and simplification of discourse, reasoning and computation.

One such convenience, as you rightfully wonder, is having a uniform notation for all strings, including the empty string. This can be achieved in several ways, whether on paper or in the computer. Terminating strings with a special symbol supposed not to belong to the set of symbols included in the strings is one way of doing it. I guess this is what you suggest with EOL. This was done some 45 years ago by Denis Ritchie for the programming language C, except that he used the byte 0, also noted NUL or ^@, rather than EOL.

In text it can be done with surrounding quotes, or with a final turnstyle $\dashv$. Note however that while the $\dashv$ alone will denote the empty string, it terminates then all strings, which is not the case for the use of the letter ε. They do not play exactly the same syntactic role.

In principle, such a termination symbol as EOL, ^@ or $\dashv$ cannot be also a symbol belonging to a string, unless you add more complex representation mechanisms.

In the computer, the null reference string could be used to represent the empty string. Otherwise it is only a programming concept that has nothing to do with the abstract concept of string.

However your question was a bit confusing and not too well stated. Talking of a "separate concept" hints at semantic issues rather than syntactic reresentation. And you were mixing textual, printed representations, which use εbut not EOL, with computer representation which do the opposite.

## With many more details

This is a strange question. In its way, it also raises one or two fundamental issues about mathematics.

Understanding such issues is non obvious, as witnessed by the inadequacies of some answers given by obviously competent users, and the inadequacies of the question itself. This is what attracted me to this question.

These two issues are concerned with :

• proper understanding of the respective roles and uses of syntax and semantics in mathematics and programming;

• proper understanding of the effect of "removing a concept from an existing theory".

The second issue, which has to do with semantics, has probably been addressed by logicians, and possibly by historians of science. But I do not recall seeing it formally addressed (or possibly I did not recognized it).

A confusion between syntax and semantics probably arose from the fact that the OP talks of a "separate concept" where he should rather talk of a "separate notation". Such a mistake is probably fair in his case as he is trying to understand issues. But it further confused some users who answered, clearly Yuval Filmus and myself, as we took the word "concept" for what it is supposed to mean.

I realize now that the next paragraph is not about the question you intended; but it is the question you wrote, and which is to be understood as semantics, and was by several people, while you meant syntax (to be addressed in the syntax part below).

Let's start with your question "Why do you need a separate concept, that of 'empty string'?", which I understood as: "could we use strings, in theory and in programming, without ever considering the empty string?", as apparently did Yuval Filmus.

The fact is, we often do not need the empty string, but it is generally more convenient to have it. Most of the theory could probably be developed without ever considering empty strings. After all, a lot of arithmetics was developed by the Greeks without considering zero as a number. Zero was introduced syntactically and semantically only a few centuries later in India. Extending the number system is not just introducing new concepts, but also a way of simplifying the understanding and use of old concepts. Introducing zero and the negative numbers made it easier to understand the properties of the natural positive numbers, and so on. Some properties of functions on the reals (such as convergence of series) are much easier to analyze and understand when you consider the extension to complex numbers.

So introducing new concepts and extensions in mathematics is often a good way of making theories simpler (and usually more powerful for expressing problems).

Introducing the empty string along with "natural strings" will simplify theories built on strings, and that is good enough a reason. Typically, as stated in other answers, having the empty string enables us to consider strings as representatives (models) of well known algebraic structures (monoids), and apply directly all known results about such structures. Indeed, as noted by J.-E. Pin, the empty string is directly related to the concatenation operation on strings (and I would add, in the same way that zero is related to the addition of integers).

We do not or may not need the empty string, but it is a lot more convenient to do mathematics with it than without it. And this is also true of programming (which is a form of mathematics aiming at producing constructive proofs).

A matter of consistency

However I disagree with the answer of Yuval Filmus regarding the effect of not allowing for the concept of an empty string, in the same way that the Greeks would not consider a number zero. Introducing zero as a new number would not have been acceptable if it had changed the known results of arithmetics. At best it would have been considered a different theory, with its own purpose.

Similarly, a theory of strings should give consistent results whether it allows for the empty string or not. But both approaches should use consistent definitions for that to be apparent and meaningful, and Yuval Filmus did not do that.

When the empty string is allowed, the usual definition of prefix is:

A string u is a prefix of a string v iff there is a string w such that u.w=v

where the dot denotes the string concatenation. This allows for a string being a prefix of itself by taking w=ε (the empty string). Then you can define:

A string u is a proper prefix of a string v iff it is a prefix of v and not equal to v.

However, when the empty string is not allowed, you have to state these definitions consistently, but differently. For example:

A string u is a proper prefix of a string v iff there is a string w such that u.w=v

Note that w must have at least one symbol. Then you can define:

A string u is a prefix of a string v iff u is a proper prefix of v or u=v.

With such consistent definitions, a word remains a prefix of itself, even when the empty string is not allowed in the theory.

So the point to be made is not that not allowing the empty string changes the properties of strings (at least not in such a trivial way) as asserted by Yuval Filmus. The point is much more that it makes the study of strings more complicated, in the same way that arithmetics is more complicated when you cannot talk of zero.

The second issue is syntactic. How should strings be represented, on paper or in the computer. In particular, assuming we agree that it is useful to have the concept of an empty string, how should it be represented syntactically so that we can talk or write about it.

The question actually arises for all mathematical concepts: how should they be represented so that we can talk or write about them, and do so as conveniently as possible. Much of the evolution of mathematics is also related to improvement of syntax, of the representation of concepts. A trivial example is the awkwardness of doing arithmetics with the ancient Roman representation of integers.

A first answer regarding the empty string is that you may want that to be consistent with the representation of other strings. Typically, the representation of a string will include the sequence of symbols in the strings plus some additional notation, such as quotes : "gattaca" for example. It then becomes quite natural to represent the empty string as "".

If you rather represent the above example as gattaca$\dashv$, then the natural representation for the empty string is $\dashv$ (as noted implicitly by David Richerby).

So the question about the need to introduce a separate notation (rather than a separate concept, as actually written) has a negative answer. No, it is not needed. Uniform notation, uniform representation, is possible for all strings, including the empty string.

However, if you simply represent the string by the sequence of included symbols, such as gattaca, with no other characters, then the empty string would become invisible syntactically, which is rather inconvenient. Then it is necessary to introduce some specific notation, such as the Greek letter ε or some other name.

Similarly, when studying strings abstractedly, it is a bit awkward to use "" to represent the empty string, if only because it does not make for nice and clear sentences in oral speech, when scientists talk to each other, which is supposed to happen on occasion. Hence it is nicer to give it a name. Saying empty string might do, but is awkward in writing. Hence the habit of using a single letter symbol as is often done in mathematics to denote entities of specific relevance,

The suggestion to represent the empty word by EOL is essentially the same as representing it by $\dashv$. It is simply a representation of strings with a special terminating character. EOL is just a special character "somehow available in computers".

As noted above for Roman integer arithmetics, the choice of a representation should be dictated by convenience, expecially in an algorithmic environment. There are many way to represent strings in general, and the empty string in particular, in the computer. From a theoretical standpoint, it does not matter much which you choose. From a practical standpoint, it is essential to choose one that will make string operations and manipulation more efficient. This is a basic issue in any class on algorithms and data structures.

## On the confusion of syntax and semantics

The answer by David Richerby is interesting for its confusion of syntax and semantics.

He tries to introduce the syntactic use of EOL suggested in the question, which he replaces by the symbol $\dashv$, but he strangely mixes it with the definition of the semantic domain of strings, making what is supposed to be only a notation part of that semantic domain.

His second definition should actually have been the following:

An alphabet is a finite set $\Sigma$ of symbols. A string $s$ over the alphabet $\Sigma$ is a finite sequence of $\ell$ symbols $s_i$, where $0\le\ell$, $1\le i\le \ell$ and $s_i\in\Sigma$ for all values of $i$. It is noted $s_1\dots s_\ell\dashv$ where $\dashv$ is a special character not denoting a symbol in $\Sigma$. We write $|s|$ for the length of $s$, defined by $|s_1\dots s_\ell\dashv|=\ell$. A substring of $s_1\dots s_\ell\dashv$ is any string $s_i\dots s_j\dashv$, where $1\leq i\leq j\leq \ell$. The concatenation of strings $s_1\dots s_\ell\dashv$ and $t_1\dots t_m\dashv$ is the string $s_1\dots s_\ell t_1\dots t_m\dashv$ of length $\ell+m$.
Note that as a consequence, the unique string of length zero is denoted  $\dashv$.

This definition is just a notational variant of the conventional definition given by David Richerby. It does not introduce any complexity or "extra fiddliness" and changes nothing to automata theory, for the simple reason that $\dashv$ is part of the notation, not a symbol in the strings. And it does give a uniform notation for all strings, including the empty one.

Yuval Filmus makes a similar error in his second remark, since EOL is intended as a syntactic notational device for representing strings, not as a symbol in strings, while $\{0,1\}$ concerns the list of symbols that can constitute strings, semantically.