Leeres Wort

Leeres Wort

Das leere Wort ist in der Theoretischen Informatik 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.

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 \epsilon als andere Schreibweise des Epsilon, e (ebenfalls für „empty“) und 1 als Einselement eines multiplikativ geschriebenen Monoids.

Merkmale

  • | ε | = 0
Die Länge des leeren Wortes ist stets 0. Diese Eigenschaft folgt direkt aus der Definition.
  • \forall w \in \Sigma^*: \varepsilon w = w \varepsilon = w
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.
  • \varepsilon \in \Sigma^*
Das leere Wort ε ist Element der Kleeneschen Hülle über jedes beliebige Alphabet Σ. Anders ausgedrückt ist das leere Wort in der Menge aller Wörter über Σ.
  • εR = ε
Das leere Wort ist identisch mit seiner Spiegelung und damit ein Palindrom.

Weitere Merkmale bei speziellen Anwendungen

Ein Automat, der das leere Wort unter Verwendung einer ε-Transition akzeptiert

[ε] = L: 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 Tupel (q1,ε,q2) aus der Übergangsrelation Δ mit Zuständen q1,q2. Ein solcher Übergang bedeutet, dass der Automat seinen Zustand von q1 nach q2 ä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.

Literatur

Weblinks

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

Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • leeres Wort — См. parola vuota …   Пятиязычный словарь лингвистических терминов

  • Wort — Satzpartikel; Satzteil * * * Wort [vɔrt], das; [e]s, Wörter [ vœrtɐ] und e: 1. a) <Plural Wörter, selten e> kleinste selbstständige sprachliche Einheit, die eigene Bedeutung oder Funktion hat: ein mehrsilbiges, zusammengesetztes Wort;… …   Universal-Lexikon

  • Wort — Es in Worten haben (auch mit dem Zusatz: wie das Eichhörnchen im Schwanz) sagt man von einem, der mit hoher Gönnermiene in beredten, schönen Worten etwas verspricht, worauf nicht zu bauen ist, dessen ganze Stärke also die Worte sind, wie die… …   Das Wörterbuch der Idiome

  • Konkatenation (Wort) — In der theoretischen Informatik ist ein Wort eine endliche Folge von Symbolen (Zeichenkette) aus einem Alphabet. Die Anzahl der Symbole eines Wortes w ist ihre Länge und wird mit | w | bezeichnet. Ein besonderes Wort ist das leere Wort, welches… …   Deutsch Wikipedia

  • Potenz (Wort) — In der theoretischen Informatik ist ein Wort eine endliche Folge von Symbolen (Zeichenkette) aus einem Alphabet. Die Anzahl der Symbole eines Wortes w ist ihre Länge und wird mit | w | bezeichnet. Ein besonderes Wort ist das leere Wort, welches… …   Deutsch Wikipedia

  • Spiegelung (Wort) — In der theoretischen Informatik ist ein Wort eine endliche Folge von Symbolen (Zeichenkette) aus einem Alphabet. Die Anzahl der Symbole eines Wortes w ist ihre Länge und wird mit | w | bezeichnet. Ein besonderes Wort ist das leere Wort, welches… …   Deutsch Wikipedia

  • Quadratfreies Wort — Unter einem quadratfreien Wort (engl. squarefree word) versteht man in der Theoretischen Informatik ein Wort, das kein (nicht leeres) Quadrat eines anderen Wortes enthält. Inhaltsverzeichnis 1 Definition 2 Eigenschaften 3 Weblinks …   Deutsch Wikipedia

  • Der Staatsanwalt hat das Wort — Seriendaten Originaltitel Der Staatsanwalt hat das Wort Produktionsland DDR (1990/1991: Deutschland) …   Deutsch Wikipedia

  • Denn eben, wo Begriffe fehlen, da stellt ein Wort zur rechten Zeit sich ein —   Dieses Zitat stammt aus Goethes Faust I. Im zweiten Teil der Studierzimmerszene rät Mephisto dem Schüler, sich beim Theologiestudium möglichst eng an die Worte eines Lehrmeisters zu halten. Auf den Einwand des Schülers »Doch ein Begriff muss… …   Universal-Lexikon

  • Endlicher Abschluss — Die Kleenesche Hülle (auch endlicher Abschluss, Kleene * Abschluss oder Verkettungshülle genannt) eines Alphabets Σ oder einer formalen Sprache L ist die Menge aller Wörter, die durch beliebige Konkatenation (Verknüpfung) von Symbolen des… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”