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?
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$.
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.
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:
That also becomes more fiddly with terminated strings:
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).
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.
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.
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.
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.
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.
J.-E. Pin's answer is quite correct, but it addresses only one part of the question, regarding the importance of the empty string. It does not address the possibility of a uniform notation.
The answers of Yuval Filmus and David Richerby confusing syntax and semantics, thus erroneously rejecting the suggestion of the OPś question to use EOL. Also Yuval Filmus'argument to assert the semantic importance of the empty string is very disputable. Though it deos make some sense, David Richerby's remark on the use of the null reference is also somewhat unwarranted: it could well be used to represent the empty string, provided the code is written accordingly.
The answer by Pseudonym is theoretical overkill regarding the importance of the empty string in formal language, but does not actually discuss the issues raised by the question.
As for my own answer, I can only hope it addresses adequately the issues and contains no error, but it is far far too long.
