- Leerstring
-
Das leere Wort ist in der Theoretischen Informatik und in der Praktischen Informatik ein Wort, das aus keinem einzigen Zeichen besteht, also eine Zeichenkette der Länge 0 (auch Leerstring genannt). In vielen Programmiersprachen wird ein solcher String durch ein Literal dargestellt, bei dem die beiden Anfangs- und Endzeichen, die eine Zeichenkette einschließen, unmittelbar aufeinander folgen, z. B. "" in Perl oder Java.
Inhaltsverzeichnis
Definition
Das leere Wort über dem Alphabet Σ ist eine Folge von Elementen aus Σ der Länge 0.
Schreibweise
Das leere Wort wird meist mit dem griechischen Buchstaben
(Epsilon für Englisch „empty“) dargestellt, oft findet sich dafür aber auch der griechische Buchstabe λ (Lambda, vom Deutschen „leer“). Andere übliche Darstellungen sind ε, e (ebenfalls für „empty“) und 1 (als Einselement eines multiplikativ geschriebenen Monoids).
Merkmale
Die Länge des leeren Wortes ist stets 0. Diese Eigenschaft folgt direkt aus der Definition.
Das leere Wort bildet bei der Konkatenation von Wörtern das neutrale Element, sprich, die Verkettung eines beliebigen Wortes w über ein beliebiges Alphabet Σ mit
ergibt stets wieder w.
Das leere Wort
ist niemals Element eines Alphabets Σ. Das würde der Definition widersprechen, die
gerade als das Fehlen jeglicher Symbole aus Σ definiert.
Das leere Wort
ist Element der Kleeneschen Hülle über jedes beliebige Alphabet Σ.
Das leere Wort ist identisch mit seiner Spiegelung und damit ein Palindrom.
Spezielle Merkmale bei speziellen Anwendungen
Betrachtet man die Äquivalenzklassen einer formalen Sprache L bezüglich der Nerode-Relation ~, so bildet
stets eine Äquivalenzklasse, die exakt L entspricht. Demnach beträgt der Index von L bezüglich ~ stets mindestens 1, in Zeichen ind(L) > = 1. Daraus wiederum lässt sich folgern, dass ein Deterministischer endlicher Automat, der L akzeptiert, aus mindestens einem Zustand bestehen muss.
-Übergänge in Nichtdeterministischen endlichen Automaten sind Argumentpaare (q,a) der Übergangsfunktion δ mit
und
. Ein solcher Übergang δ(q1,δ) = q2 bedeutet, dass der Automat seinen Zustand von q1 nach q2 ändern kann, ohne dass ein Zeichen eingegeben wird.
-Übergänge sind damit die Grundlage des Nichtdeterminismus. Sie werden im Graphen als Kanten kenntlich gemacht, die mit einem
beschriftet sind.
Wikimedia Foundation.