imported>BoyVoEffi: Grammatikfehler korrigiert, leichte Vereinfachung der Formulierung

2024-11-26T10:50:56Z

Grammatikfehler korrigiert, leichte Vereinfachung der Formulierung

Neue Seite

Das '''leere Wort''' ist in der [[Theoretische Informatik|Theoretischen]] und in der [[Praktische Informatik|Praktischen Informatik]] ein [[Wort (Theoretische Informatik)|Wort]], das aus keinem einzigen Zeichen besteht, also die Länge 0 hat. Es wird auch ''Leerstring'' genannt. In vielen Programmiersprachen wird ein solcher [[Zeichenkette|String]] durch ein [[Literal]] dargestellt, bei dem die beiden Anfangs- und Endzeichen, die eine Zeichenkette einschließen, unmittelbar aufeinander folgen, z. B. "" in [[Perl (Programmiersprache)|Perl]] oder [[Java (Programmiersprache)|Java]].

== Definition ==
Das leere Wort über dem [[Alphabet (Informatik)|Alphabet]] <math>\Sigma</math> ist eine Folge von Elementen aus <math>\Sigma</math> der Länge 0.

== Schreibweise ==
Das leere Wort wird meist mit dem griechischen Buchstaben <math>\varepsilon</math> ([[Epsilon]] für Englisch „empty“) dargestellt, oft findet sich dafür aber auch der griechische Buchstabe <math>\lambda</math> ([[Lambda]], vom Deutschen „leer“). Andere übliche Darstellungen sind <math>\epsilon</math> als andere Schreibweise des Epsilon, <math>e</math> (ebenfalls für „empty“) und <math>1</math> als [[Einselement]] eines multiplikativ geschriebenen [[Monoid]]s.

== Merkmale ==
*<math>|\varepsilon| = 0</math>
:Die Länge des leeren Wortes ist stets 0. Diese Eigenschaft folgt direkt aus der Definition.

*<math>\forall w \in \Sigma^*: \varepsilon w = w \varepsilon = w</math>
:Das leere Wort bildet bei der [[Konkatenation (Wort)|Konkatenation]] von Wörtern das [[Neutrales Element|neutrale Element]], sprich, die Verkettung eines beliebigen Wortes <math>w</math> über ein beliebiges Alphabet <math>\Sigma</math> mit <math>\varepsilon</math> ergibt stets wieder <math>w</math>. Die Menge der Wörter, welche über dem Alphabet gebildet werden können, ist die [[Kleenesche und positive Hülle|Kleenesche Hülle]] <math>\Sigma^*</math>.

*<math>\varepsilon \in \Sigma^*</math>
:Das leere Wort <math>\varepsilon</math> ist Element der [[Kleenesche Hülle|Kleeneschen Hülle]] <math>\Sigma^*</math> über jedem beliebigen Alphabet <math>\Sigma</math>. Das leere Wort ist also ein Wort über jedem Alphabet.

*<math>\varepsilon^R = \varepsilon</math>
:Das leere Wort ist identisch mit seiner [[Spiegelung (Wort)|Spiegelung]] und damit ein [[Palindrom (Theoretische Informatik)|Palindrom]].

== Weitere Merkmale bei speziellen Anwendungen ==
[[Datei:FA_regexp_accept_null.svg|miniatur|Ein Automat, der das leere Wort unter Verwendung einer <math>\varepsilon</math>-Transition akzeptiert]]
Die <math>\varepsilon</math>-Übergänge in [[Nichtdeterministischer endlicher Automat|nichtdeterministischen endlichen Automaten]] sind Tupel <math>(q_1, \varepsilon,q_2)</math> aus der Übergangsrelation <math>\Delta</math> mit Zuständen <math>q_1, q_2</math>. Ein solcher Übergang bedeutet, dass der Automat seinen Zustand von <math>q_1</math> nach <math>q_2</math> ändern kann, ohne dass ein Zeichen gelesen wird. <math>\varepsilon</math>-Übergänge sind damit einer der Gründe für Nichtdeterminismus. Sie werden im Graphen als Kanten kenntlich gemacht, die mit einem <math>\varepsilon</math> beschriftet sind.

Auch bei [[Kellerautomat]]en sind <math>\varepsilon</math>-Ü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 ==
* [[John E. Hopcroft]], [[Jeffrey Ullman|Jeffrey D. Ullman]]: ''Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie.'' 2. Auflage. Pearson Studium, Reading 2002, ISBN 3-8273-7020-5
== Weblinks ==
{{Wiktionary|leeres Wort}}

[[Kategorie:Theorie formaler Sprachen]]
[[Kategorie:Compilerbau]]

Leeres Wort - Versionsgeschichte

imported>BoyVoEffi: Grammatikfehler korrigiert, leichte Vereinfachung der Formulierung