patternModerate
Importance of the empty string
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?
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$.
$$
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.