Das leere Wort ist in der Theoretischen und in der Praktischen Informatik ein Wort, das aus keinem einzigen Zeichen besteht, also die Länge 0 hat. Es wird 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.
Definition Bearbeiten
Das leere Wort über dem Alphabet ist eine Folge von Elementen aus der Länge 0.
Schreibweise Bearbeiten
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 als andere Schreibweise des Epsilon, (ebenfalls für „empty“) und als Einselement eines multiplikativ geschriebenen Monoids.
Merkmale Bearbeiten
Weitere Merkmale bei speziellen Anwendungen Bearbeiten
Die -Übergänge in nichtdeterministischen endlichen Automaten sind Tupel aus der Übergangsrelation mit Zuständen . Ein solcher Übergang bedeutet, dass der Automat seinen Zustand von nach ändern kann, ohne dass ein Zeichen gelesen wird. -Übergänge sind damit einer der Gründe für Nichtdeterminismus. Sie werden im Graphen als Kanten kenntlich gemacht, die mit einem beschriftet sind.
Auch bei Kellerautomaten sind -Übergänge möglich und bedeuten, dass durch jene Zustandswechsel das Eingabewort nicht abgearbeitet wird. Wird beim Lesen des Kellerinhalts bei einem Übergang das oberste Symbol durch das leere Wort ersetzt, wird es damit aus dem Keller entfernt. Schließlich symbolisiert das leere Wort den leeren Keller, der eines von zwei möglichen Akzeptanzkriterien bei Kellerautomaten ist.
Literatur Bearbeiten
- John E. Hopcroft, Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. 2. Auflage. Pearson Studium, Reading 2002, ISBN 3-8273-7020-5