Leeres Wort - LinkFang.de





Leeres Wort


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

Das leere Wort über dem 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 Monoids.

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 von Wörtern das 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 Hülle [math]\Sigma^*[/math].
  • [math]\varepsilon \in \Sigma^*[/math]
Das leere Wort [math]\varepsilon[/math] ist Element der Kleeneschen Hülle [math]\Sigma^*[/math] über jedes beliebige Alphabet [math]\Sigma[/math]. Anders ausgedrückt ist das leere Wort in der Menge aller Wörter über [math]\Sigma[/math].
  • [math]\varepsilon^R = \varepsilon[/math]
Das leere Wort ist identisch mit seiner Spiegelung und damit ein Palindrom.

Weitere Merkmale bei speziellen Anwendungen

Die [math]\varepsilon[/math]-Übergänge in 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 Kellerautomaten 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

Weblinks

 Wiktionary: leeres Wort – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

Kategorien: Compilerbau | Theorie formaler Sprachen

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Leeres Wort (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.