Welche Bedeutung hat eine leere Zeichenfolge in CS (und insbesondere in formalen Sprachen) im Sinne einer Zeichenfolge, die sich von einer Nullreferenzzeichenfolge unterscheidet?

Warum brauchen Sie ein separates Konzept, das der "leeren Zeichenfolge", die sogar einen eigenen griechischen Buchstaben (ε) hat?

Könnte nicht nur ein EOL-Charakter es ersetzen?

Es gibt eine mathematische Bedeutung für die leere Zeichenfolge. In der Tat ist das Verkettungsprodukt von Wörtern eine assoziative Operation. Diese Operation hat aber auch ein neutrales Element , nämlich das leere Wort. Aus diesem Grund wird das leere Wort auch häufig mit bezeichnet$1$, was es einem erlaubt, für jedes Wort zu schreiben $u$,

$$1 \cdot u = u = u \cdot 1$$

Natürlich, wenn das Alphabet ist $\{0, 1\}$Es ist keine gute Idee, das leere Wort mit zu bezeichnen $1$ und dies ist wahrscheinlich der Grund, warum die Notation $\varepsilon$ (oder manchmal $\lambda$) wurde vorgestellt. Aber wie Yuval Filmus betonte, ist das leere Wort ein Wort der Länge$0$Das heißt, es enthält keinen Buchstaben.

Es ist sicherlich beunruhigend, das leere Wort mit zu bezeichnen $1$ (oder durch einen griechischen Brief $\varepsilon$ oder $\lambda$), aber Sie müssen es als konventionelle Notation nehmen, genauso wie Sie die leere Menge mit bezeichnen $\emptyset$.

Die leere Zeichenfolge ist wie Null. Es repräsentiert "nichts", ist aber ein grundlegendes Konzept. Als sehr einfaches Beispiel ein Wort$a$ ist ein Präfix eines Wortes $b$ wenn $b = aw$ für ein Wort $w$. Wenn Sie die leere Zeichenfolge nicht zulassen, ist ein Wort kein Präfix für sich.

Das EOL-Zeichen ist ein Zeichen in einem bestimmten Zeichensatz. Wenn wir an Strings vorbei interessiert sind$\{0,1\}$Wir haben keine EOL. Außerdem ist EOL ein Zeichen, sodass eine aus EOL bestehende Zeichenfolge nicht leer ist.

Die Verwendung eines Zeilenendezeichens (EOL) entspricht der Ausdruckskraft - alles, was Sie mit dem leeren Wort tun können $\varepsilon$Sie könnten stattdessen neu definieren, um mit EOL zu tun - aber es zu verwenden, wäre ein monumentaler Schmerz im Hintern. Die herkömmlichen Definitionen sind:

Ein Alphabet ist eine endliche Menge$\Sigma$von Symbolen. Eine Zeichenfolge $s$ über das Alphabet $\Sigma$ ist eine endliche Folge $s_1\dots s_\ell$, wo jeder $s_i\in\Sigma$. Wir schreiben$|s|$für die Länge von$s$mit $|s_1\dots s_\ell|=\ell$;; Das eindeutige Wort der Länge Null wird bezeichnet $\varepsilon$. Ein Teilstring von$s_1\dots s_\ell$ ist eine beliebige Zeichenfolge $s_i\dots s_j$, wo $1\leq i\leq j\leq \ell$. Die Verkettung von Strings$s_1\dots s_\ell$ und $t_1\dots t_m$ ist die Zeichenfolge $s_1\dots s_\ell t_1\dots t_m$ von Länge $\ell+m$.

Vergleichen Sie dies mit:

Lassen $\dashv$ein unterschiedliches Zeilenende- Symbol sein. Ein Alphabet ist eine endliche Menge $\Sigma$ von Symbolen so, dass ${\dashv}\in\Sigma$. Eine Zeichenfolge $s$ über das Alphabet $\Sigma$ ist eine endliche Folge $s_1\dots s_\ell$ wo $s_i\in\Sigma\setminus\{{\dashv}\}$ zum $i<\ell$ und $s_\ell={\dashv}$. Wir schreiben$|s|$für die Länge von$s$mit $|s_1\dots s_\ell|=\ell-1$. Ein Teilstring von$s_1\dots s_\ell$ ist eine beliebige Zeichenfolge $s_i\dots s_j{\dashv}$, wo $1\leq i\leq j< \ell$. Die Verkettung von Strings$s_1\dots s_\ell$ und $t_1\dots t_m$ ist die Zeichenfolge $s_1\dots s_{\ell-1} t_1\dots t_m$ von Länge $\ell+m-2$.

Beachten Sie die zusätzliche Fummelei und das Potenzial für Off-by-One-Fehler, insbesondere bei der Definition der Verkettung. Erwägen Sie auch, Automaten über diese terminierten Zeichenfolgen zu definieren. Zusätzlich zur Überprüfung, ob die Eingabe die für die Sprache erforderlichen Eigenschaften aufweist, muss jeder Automat jetzt überprüfen, ob das letzte Zeichen der Eingabe ist${\dashv}$, was (glaube ich) jedem Automaten zwei Zustände hinzufügt.

Die leere Zeichenfolge $\varepsilon$hat die gleiche Rolle wie Null in den natürlichen Zahlen. Es ist die Identität für die grundlegendste Operation (Verkettung für Strings, Addition für Naturals). Dies ist wichtig, wenn Sie eine algebraische Struktur wie Gruppen oder Monoide erstellen möchten , die Zugriff auf einen großen Bereich potenziell nützlicher mathematischer Ergebnisse bietet. Einfacher ausgedrückt ist dies eine hervorragende Grundlage für Induktionen, da die Hypothese für die leere Zeichenfolge häufig trivial ist. Wenn Sie eine Induktion für Zeichenfolgen durchführen, verwenden Sie implizit die folgende induktive Definition von$\Sigma$-strings:

• $\varepsilon$ ist ein $\Sigma$-string;
• wenn $s$ ist ein $\Sigma$-string und $\sigma\in\Sigma$, dann $s\sigma$ ist ein $\Sigma$-string.

Das wird auch bei terminierten Zeichenfolgen fummeliger:

• ${\dashv}$ ist ein $\Sigma$-string;
• wenn $s{\dashv}$ ist ein $\Sigma$-string und $\sigma\in\Sigma\setminus\{{\dashv}\}$, dann $s\sigma{\dashv}$ ist ein $\Sigma$-string.

Natürlich könnten Sie es auch umgekehrt machen und sagen, wenn $s$ ist eine Zeichenfolge, dann ist es auch $\sigma s$. Zu diesem Zeitpunkt gibt es wenig Auswahl zwischen terminierten und nicht terminierten Zeichenfolgen, aber Ihre Induktion ist möglicherweise besser geeignet, um Zeichen am Ende als am Anfang hinzuzufügen.

Abgeschlossene Zeichenfolgen eignen sich gut zum Programmieren, sind jedoch für die Mathematik nicht gut geeignet. Wenn Sie programmieren, müssen Sie wissen, wann die Zeichenfolge ist$s_1\dots s_\ell$endet; Wenn Sie Mathematik machen, ist es offensichtlich, dass$s_\ell$ ist das letzte Zeichen aus der Art und Weise, wie die Zeichenfolge geschrieben wird.

---

Ich habe gerade bemerkt, dass Sie nach dem Unterschied zwischen einer Nullreferenz und der leeren Zeichenfolge fragen. Eine Nullreferenz ist überhaupt keine Zeichenfolge. Die leere Zeichenfolge ist eine Zeichenfolge, enthält jedoch keine Zeichen. Wenn Sie möchten, ist es der Unterschied zwischen einem leeren Blatt Papier (leere Zeichenfolge) und überhaupt keinem Papier (Nullreferenz).

Kurze Antwort: Die leere Menge (dh die Menge von Zeichenfolgen, die keine Zeichenfolgen enthält) ist wie Null, aber die leere Zeichenfolge (dh die Menge von Zeichenfolgen, die eine Zeichenfolge mit der Länge Null enthält) ist wie Eins.

Eine Möglichkeit, formale Sprachen zu axiomatisieren, ist das idempotente Semiring. Ein Semiring ist eine Struktur mit zwei binären Operationen$+$ und $\cdot$und zwei unterscheidbare Elemente $0$ und $1$und gehorcht den folgenden Axiomen. Erst einmal,$+$ ist ein kommutatives Monoid mit Identität $0$::

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

Zweitens, $\cdot$ ist ein Monoid mit Identität $1$::

$$(A\cdot B)\cdot C = A\cdot(B\cdot C)$$ $$1\cdot A = A\cdot 1 = A$$ Die Multiplikation links und rechts verteilt sich auf die Addition: $$A\cdot (B + C) = (A\cdot B) + (A\cdot C)$$ $$(A + B)\cdot C = (A\cdot C) + (B\cdot C)$$ Multiplikation mit 0 vernichtet: $$0\cdot A = A\cdot 0 = 0$$ und schließlich ist die Hinzufügung idempotent: $$A + A = A$$

"Addition" kann als Set Union interpretiert werden und "Multiplikation" kann als String-Verkettung interpretiert werden.

Oh, und die Verbindung geht sehr tief. Der Kleene-Verschlussoperator, der intuitiv definiert ist als:

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

verhält sich wie Potenzierung. Denken Sie an die Potenzreihen von$e^x$und die Tatsache, dass Addition idempotent ist.

Terminalzeichen verhalten sich wie Variablen. Insbesondere können wir die Bewertung bei Null definieren:

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

Gegeben ein regulärer Ausdruck $E$, $E(0)$ entweder $0$ oder $1$. Es ist$1$ wenn die leere Zeichenfolge Mitglied von ist $E$, und $0$ Andernfalls.

Wir können auch ein Derivat definieren, das als Brzozowski-Derivat bezeichnet wird:

$$\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^*$$

Die einzige ungerade Regel hier ist die für die Multiplikation. Es ist fast wie die bekannte Produktregel; Der Unterschied ist auf die Tatsache zurückzuführen, dass die Verkettung nicht kommutativ ist.

Was die Ableitung intuitiv bedeutet, ist das $\frac{\partial E}{\partial a}$ ist die Menge der Zeichenfolgen in $E$ die mit dem Symbol beginnen $a$, aber damit $a$entfernt. Damit$a \frac{\partial E}{\partial a}$ ist die Menge der Zeichenfolgen in $E$ die beginnen mit $a$.

Denken Sie einen Moment darüber nach, wenn ${a\ldots z}$ ist das Alphabet, dann:

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

Dies ist Taylors Theorem, nur für reguläre Sprachen. Darüber hinaus ist es auch eine Regel, DFAs direkt aus regulären Ausdrücken zu erstellen!$E(0)$ ist $1$ genau dann, wenn der Anfangszustand ein Endzustand ist und die anderen Begriffe die Übergänge sind.

Eine bemerkenswerte Sache dabei ist, dass die bekannten Operatoren für reguläre Ausdrücke (plus einige weniger bekannte Operatoren wie Satzschnittpunkt und Satzdifferenz) vollständig durch ihre Ableitungen plus ihre Bewertung bei Null bestimmt werden. Dies ist, was wir vom Grundsatz der Analysis erwarten würden, aber es ist interessant, es auch hier zu sehen.

Übrigens lässt sich diese Theorie auch auf kontextfreie und rekursive Sprachen skalieren, aber Sie brauchen ein bisschen mehr Maschinerie für das, worauf ich hier nicht eingehen werde.

Eine grundlegende Frage zur Mathematik

Diese Antwort wurde neu organisiert, nachdem das OP genauere Angaben zur Bedeutung und Absicht seiner Frage gemacht hatte. Ich kommentiere hier auch andere Antworten, da es schwierig ist, dies im üblichen Kommentarformat zu tun. Wenn Sie sie kommentieren, erhalten Sie auch einen zusätzlichen Einblick in die relevanten Themen.

In einer Nussschale

Ihre Intuition ist ganz richtig, dass die leere Zeichenfolge eine besondere Rolle beim Studium von Zeichenfolgen und formalen Sprachen spielt, und das ist der Grund, warum sie häufig einen speziellen Namen oder eine spezielle Notation erhält. Zeichenfolgen über einem bestimmten Satz von Symbolen bilden eine algebraische Struktur, die als Monoid bezeichnet wird, wobei die Verkettungsoperation ein neutrales Element aufweist: die leere Zeichenfolge. Siehe die Antwort von J.-E. Pin .

Sie haben auch Recht, dass es viele andere Notationen oder Darstellungen dafür geben könnte. Die Wahl der Darstellung wird durch Zweckmäßigkeit, Übersichtlichkeit und Vereinfachung des Diskurses, der Argumentation und der Berechnung bestimmt.

Wie Sie sich zu Recht fragen, besteht eine solche Annehmlichkeit darin, für alle Zeichenfolgen, einschließlich der leeren Zeichenfolge, eine einheitliche Notation zu haben. Dies kann auf verschiedene Arten erreicht werden, ob auf Papier oder im Computer. Das Beenden von Zeichenfolgen mit einem speziellen Symbol, das nicht zu den in den Zeichenfolgen enthaltenen Symbolen gehören soll, ist eine Möglichkeit, dies zu tun. Ich denke, das schlagen Sie mit EOL vor. Dies wurde vor etwa 45 Jahren von Denis Ritchie für die Programmiersprache C durchgeführt, außer dass er das Byte 0, ebenfalls NUL oder ^ @, anstelle von EOL verwendete.

Im Text kann dies mit umgebenden Anführungszeichen oder mit einem endgültigen Drehstil erfolgen $\dashv$. Beachten Sie jedoch, dass während der$\dashv$allein bezeichnet die leere Zeichenfolge, es werden dann alle Zeichenfolgen beendet, was bei der Verwendung des Buchstabens ε nicht der Fall ist. Sie spielen nicht genau die gleiche syntaktische Rolle.

Grundsätzlich kann ein solches Beendigungssymbol wie EOL, ^ @ oder $\dashv$ kann nicht auch ein Symbol sein, das zu einer Zeichenfolge gehört, es sei denn, Sie fügen komplexere Darstellungsmechanismen hinzu.

Auf dem Computer kann die Nullreferenzzeichenfolge verwendet werden, um die leere Zeichenfolge darzustellen. Ansonsten ist es nur ein Programmierkonzept, das nichts mit dem abstrakten Konzept des Strings zu tun hat.

Ihre Frage war jedoch etwas verwirrend und nicht zu gut formuliert. Die Rede von einem " separaten Konzept " deutet eher auf semantische Fragen als auf syntaktische Repräsentation hin. Und Sie mischten gedruckte Textdarstellungen, die ε, aber nicht EOL verwenden, mit Computerdarstellungen, die das Gegenteil bewirken.

Mit vielen weiteren Details

Das ist eine seltsame Frage. Auf seine Weise wirft es auch ein oder zwei grundlegende Fragen zur Mathematik auf.

Das Verständnis solcher Probleme ist nicht offensichtlich, wie die Unzulänglichkeiten einiger Antworten offensichtlich kompetenter Benutzer und die Unzulänglichkeiten der Frage selbst belegen. Das hat mich zu dieser Frage hingezogen.

Diese beiden Themen betreffen:

• richtiges Verständnis der jeweiligen Rollen und Verwendungen von Syntax und Semantik in Mathematik und Programmierung;

• richtiges Verständnis der Wirkung des "Entfernens eines Konzepts aus einer bestehenden Theorie" .

Das zweite Problem, das mit Semantik zu tun hat, wurde wahrscheinlich von Logikern und möglicherweise von Wissenschaftshistorikern angesprochen. Aber ich kann mich nicht erinnern, dass ich es formell angesprochen habe (oder möglicherweise habe ich es nicht erkannt).

Eine Verwechslung zwischen Syntax und Semantik ergab sich wahrscheinlich aus der Tatsache, dass das OP von einem " separaten Konzept " spricht, bei dem er eher von einer " separaten Notation " sprechen sollte . Ein solcher Fehler ist in seinem Fall wahrscheinlich fair, da er versucht, Probleme zu verstehen. Aber es verwirrte einige Benutzer weiter, die antworteten, eindeutig Yuval Filmus und ich, als wir das Wort "Konzept" für das nahmen, was es bedeuten soll.

Über Semantik

Mir ist jetzt klar, dass es im nächsten Absatz nicht um die von Ihnen beabsichtigte Frage geht. Aber es ist die Frage, die Sie geschrieben haben und die als Semantik zu verstehen ist und die von mehreren Personen gestellt wurde, während Sie Syntax meinten (die im folgenden Syntaxteil behandelt werden soll).

Beginnen wir mit Ihrer Frage " Warum brauchen Sie ein separates Konzept, das der 'leeren Zeichenfolge'? ", Das ich so verstand: "Können wir Zeichenfolgen theoretisch und in der Programmierung verwenden, ohne jemals die leere Zeichenfolge zu berücksichtigen?" wie anscheinend Yuval Filmus.

Tatsache ist, dass wir die leere Zeichenfolge oft nicht benötigen , aber es ist im Allgemeinen bequemer, sie zu haben. Der größte Teil der Theorie könnte wahrscheinlich entwickelt werden, ohne jemals leere Strings zu berücksichtigen. Immerhin viel wurde von den Griechen Arithmetik entwickelt, ohne Null als Zahl zu betrachten. Zero wurde nur wenige Jahrhunderte später in Indien syntaktisch und semantisch eingeführt. Durch die Erweiterung des Zahlensystems werden nicht nur neue Konzepte eingeführt, sondern auch das Verständnis und die Verwendung alter Konzepte vereinfacht. Die Einführung von Null und den negativen Zahlen erleichterte das Verständnis der Eigenschaften der natürlichen positiven Zahlen und so weiter. Einige Eigenschaften von Funktionen auf den Reals (wie die Konvergenz von Reihen) sind viel einfacher zu analysieren und zu verstehen, wenn Sie die Erweiterung auf komplexe Zahlen betrachten.

Die Einführung neuer Konzepte und Erweiterungen in der Mathematik ist daher oft eine gute Möglichkeit, Theorien zu vereinfachen (und in der Regel leistungsfähiger, um Probleme auszudrücken).

Die Einführung der leeren Zeichenfolge zusammen mit "natürlichen Zeichenfolgen" vereinfacht Theorien, die auf Zeichenfolgen basieren, und das ist Grund genug. Wie in anderen Antworten angegeben, können wir mit der leeren Zeichenfolge normalerweise Zeichenfolgen als Repräsentanten (Modelle) bekannter algebraischer Strukturen (Monoide) betrachten und alle bekannten Ergebnisse über solche Strukturen direkt anwenden. In der Tat, wie von J.-E. Pin, die leere Zeichenfolge steht in direktem Zusammenhang mit der Verkettungsoperation für Zeichenfolgen (und ich würde hinzufügen, genauso wie Null mit der Hinzufügung von Ganzzahlen zusammenhängt).

Wir brauchen oder brauchen den leeren String nicht, aber es ist viel bequemer, damit zu rechnen als ohne. Dies gilt auch für die Programmierung (eine Form der Mathematik, die darauf abzielt, konstruktive Beweise zu erstellen).

Eine Frage der Beständigkeit

Allerdings stimme ich mit der Antwort von Yuval Filmus in Bezug auf die Wirkung der nicht für das Konzept einer leeren Zeichenfolge ermöglicht, auf die gleiche Art und Weise , dass die Griechen nicht eine Zahl Null in Betracht ziehen. Die Einführung von Null als neue Zahl wäre nicht akzeptabel gewesen, wenn die bekannten Ergebnisse der Arithmetik geändert worden wären. Bestenfalls wäre es eine andere Theorie mit eigenem Zweck gewesen.

In ähnlicher Weise sollte eine Zeichenfolgentheorie konsistente Ergebnisse liefern, unabhängig davon, ob die leere Zeichenfolge zulässig ist oder nicht. Beide Ansätze sollten jedoch einheitliche Definitionen verwenden, damit dies offensichtlich und sinnvoll ist, und Yuval Filmus hat dies nicht getan.

Wenn die leere Zeichenfolge zulässig ist , lautet die übliche Definition des Präfix :

Ein String u ist ein Präfix eines Strings v, wenn es einen String w gibt, so dass uw = v ist

Dabei bezeichnet der Punkt die Zeichenfolgenverkettung. Dies ermöglicht, dass eine Zeichenfolge ein Präfix für sich selbst ist, indem w = ε (die leere Zeichenfolge) verwendet wird. Dann können Sie definieren:

Ein String u ist ein richtiges Präfix eines Strings v, wenn es ein Präfix von v ist und nicht gleich v ist.

Allerdings , wenn die leere Zeichenkette nicht erlaubt ist , müssen Sie konsequent diese Definitionen angeben, aber anders. Zum Beispiel:

Ein String u ist ein richtiges Präfix eines Strings v, wenn es einen String w gibt, so dass uw = v ist

Beachten Sie, dass w mindestens ein Symbol haben muss. Dann können Sie definieren:

Eine Zeichenfolge u ist ein Präfix einer Zeichenfolge v, wenn u ein geeignetes Präfix von v oder u = v ist.

Bei solchen konsistenten Definitionen bleibt ein Wort ein Präfix für sich selbst, selbst wenn die leere Zeichenfolge in der Theorie nicht zulässig ist.

Es muss also nicht darauf hingewiesen werden, dass das Nichtzulassen der leeren Zeichenfolge die Eigenschaften von Zeichenfolgen ändert (zumindest nicht auf eine so triviale Weise), wie von Yuval Filmus behauptet. Der Punkt ist viel mehr, dass es das Studium von Strings komplizierter macht, genauso wie die Arithmetik komplizierter ist, wenn man nicht von Null sprechen kann.

Informationen zur Syntax

Das zweite Problem ist syntaktisch. Wie sollen Zeichenfolgen auf Papier oder im Computer dargestellt werden? Unter der Annahme, dass wir uns einig sind, dass es nützlich ist, das Konzept einer leeren Zeichenfolge zu haben, wie sollte es syntaktisch dargestellt werden, damit wir darüber sprechen oder schreiben können.

Tatsächlich stellt sich für alle mathematischen Konzepte die Frage: Wie sollen sie dargestellt werden, damit wir darüber sprechen oder schreiben können, und dies so bequem wie möglich. Ein Großteil der Entwicklung der Mathematik hängt auch mit der Verbesserung der Syntax und der Darstellung von Konzepten zusammen. Ein triviales Beispiel ist die Unbeholfenheit, mit der antiken römischen Darstellung von ganzen Zahlen zu rechnen.

Eine erste Antwort bezüglich der leeren Zeichenfolge lautet, dass Sie möchten, dass diese mit der Darstellung anderer Zeichenfolgen übereinstimmt. In der Regel enthält die Darstellung einer Zeichenfolge die Folge von Symbolen in den Zeichenfolgen sowie eine zusätzliche Notation, z. B. Anführungszeichen: " gattaca ". Es wird dann ganz natürlich, die leere Zeichenfolge als "" darzustellen.

Wenn Sie das obige Beispiel lieber als Gattaca darstellen$\dashv$, dann ist die natürliche Darstellung für die leere Zeichenfolge $\dashv$ (wie implizit von David Richerby erwähnt).

Die Frage nach der Notwendigkeit, eine separate Notation einzuführen (anstelle eines separaten Konzepts , wie es tatsächlich geschrieben wurde), hat also eine negative Antwort. Nein, es wird nicht benötigt. Eine einheitliche Notation und einheitliche Darstellung ist für alle Zeichenfolgen möglich, einschließlich der leeren Zeichenfolge.

Wenn Sie die Zeichenfolge jedoch einfach durch die Folge der enthaltenen Symbole wie Gattaca ohne andere Zeichen darstellen, wird die leere Zeichenfolge syntaktisch unsichtbar, was ziemlich unpraktisch ist. Dann ist es notwendig, eine bestimmte Notation einzuführen, wie den griechischen Buchstaben ε oder einen anderen Namen.

In ähnlicher Weise ist es beim abstrakten Studium von Zeichenfolgen etwas umständlich, "" zur Darstellung der leeren Zeichenfolge zu verwenden, schon allein deshalb, weil es in der mündlichen Rede keine schönen und klaren Sätze ergibt, wenn Wissenschaftler miteinander sprechen, was passieren soll bei Gelegenheit. Daher ist es schöner, ihm einen Namen zu geben. Das Sagen einer leeren Zeichenfolge reicht möglicherweise aus, ist jedoch schriftlich umständlich. Daher die Gewohnheit, ein einzelnes Buchstabensymbol zu verwenden, wie es in der Mathematik häufig verwendet wird, um Entitäten von spezifischer Relevanz zu bezeichnen.

Der Vorschlag, das leere Wort durch EOL darzustellen, entspricht im Wesentlichen dem Vorschlag, es durch darzustellen $\dashv$. Es ist einfach eine Darstellung von Zeichenfolgen mit einem speziellen Abschlusszeichen. EOL ist nur ein Sonderzeichen "irgendwie in Computern verfügbar".

Wie oben für die römische Ganzzahlarithmetik erwähnt, sollte die Wahl einer Darstellung durch Bequemlichkeit bestimmt werden, insbesondere in einer algorithmischen Umgebung. Es gibt viele Möglichkeiten, Zeichenfolgen im Allgemeinen und die leere Zeichenfolge im Besonderen im Computer darzustellen. Aus theoretischer Sicht spielt es keine Rolle, welche Sie wählen. Aus praktischer Sicht ist es wichtig, eine zu wählen, die String-Operationen und Manipulationen effizienter macht. Dies ist ein grundlegendes Problem in jeder Klasse zu Algorithmen und Datenstrukturen.

Über die Verwechslung von Syntax und Semantik

Die Antwort von David Richerby ist interessant für die Verwechslung von Syntax und Semantik.

Er versucht, die in der Frage vorgeschlagene syntaktische Verwendung von EOL einzuführen, die er durch das Symbol ersetzt $\dashv$, aber er mischt es seltsamerweise mit der Definition der semantischen Domäne von Strings und macht das, was nur eine Notation sein soll, zu einem Teil dieser semantischen Domäne.

Seine zweite Definition hätte eigentlich folgende sein sollen:

Ein Alphabet ist eine endliche Menge$\Sigma$von Symbolen. Eine Zeichenfolge $s$ über das Alphabet $\Sigma$ ist eine endliche Folge von $\ell$ Symbole $s_i$, wo $0\le\ell$, $1\le i\le \ell$ und $s_i\in\Sigma$ für alle Werte von $i$. Es ist notiert$s_1\dots s_\ell\dashv$ wo $\dashv$ ist ein Sonderzeichen, das kein Symbol in bezeichnet $\Sigma$. Wir schreiben$|s|$für die Länge von $s$, definiert von $|s_1\dots s_\ell\dashv|=\ell$. Ein Teilstring von$s_1\dots s_\ell\dashv$ ist eine beliebige Zeichenfolge $s_i\dots s_j\dashv$, wo $1\leq i\leq j\leq \ell$. Die Verkettung von Strings$s_1\dots s_\ell\dashv$ und $t_1\dots t_m\dashv$ ist die Zeichenfolge $s_1\dots s_\ell t_1\dots t_m\dashv$ von Länge $\ell+m$.
Beachten Sie, dass infolgedessen die eindeutige Zeichenfolge mit der Länge Null bezeichnet wird  $\dashv$.

Diese Definition ist nur eine notatorische Variante der konventionellen Definition von David Richerby. Es führt keine Komplexität oder " zusätzliche Fummelei " ein und ändert nichts an der Automatentheorie, aus dem einfachen Grund, dass$\dashv$ist Teil der Notation, kein Symbol in den Zeichenfolgen. Und es gibt eine einheitliche Notation für alle Zeichenfolgen, einschließlich der leeren.

Yuval Filmus macht in seiner zweiten Bemerkung einen ähnlichen Fehler , da EOL als syntaktisches Notationsinstrument zur Darstellung von Strings gedacht ist, nicht als Symbol in Strings$\{0,1\}$ betrifft die Liste der Symbole, die semantisch Zeichenfolgen bilden können.

Antworten zusammenfassen

J.-E. Die Antwort von Pin ist ganz richtig, aber sie behandelt nur einen Teil der Frage in Bezug auf die Wichtigkeit der leeren Zeichenfolge. Die Möglichkeit einer einheitlichen Notation wird nicht angesprochen.

Die Antworten von Yuval Filmus und David Richerby verwirren Syntax und Semantik und lehnen damit fälschlicherweise den Vorschlag der OPś-Frage ab, EOL zu verwenden. Auch das Argument von Yuval Filmus, die semantische Bedeutung der leeren Zeichenfolge zu behaupten, ist sehr umstritten. Obwohl dies durchaus sinnvoll ist, ist David Richerbys Bemerkung zur Verwendung der Nullreferenz ebenfalls etwas ungerechtfertigt: Sie könnte durchaus zur Darstellung der leeren Zeichenfolge verwendet werden, sofern der Code entsprechend geschrieben ist.

Die Antwort von Pseudonym ist ein theoretischer Overkill in Bezug auf die Bedeutung der leeren Zeichenfolge in der formalen Sprache, erörtert jedoch nicht die durch die Frage aufgeworfenen Fragen.

Was meine eigene Antwort , kann ich nur hoffen , dass es ausreichend die Probleme adressiert und enthält keine Fehler, aber es ist lange weit zu weit.