HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Importance of the empty string

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
importancetheemptystring

Problem

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?

Solution

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

Context

StackExchange Computer Science Q#19505, answer score: 13

Revisions (0)

No revisions yet.