In der Informatik ist ein Wort jede endliche Zeichenfolge, die sich aus den Zeichen eines festgelegten Alphabets zusammensetzt – etwa ein Passwort, eine Binärzahl oder eine Folge von Tastendrücken. Ob die Zeichenfolge inhaltlich einen Sinn ergibt, spielt dabei keine Rolle.

Definition

Es sei [math]\displaystyle{ \Sigma }[/math] ein Alphabet (eine endliche, nicht leere Menge von Zeichen). Ein Wort [math]\displaystyle{ w }[/math] über dem Alphabet [math]\displaystyle{ \Sigma }[/math] ist eine endliche Folge von [math]\displaystyle{ n }[/math] Zeichen [math]\displaystyle{ a_1, a_2, \dots, a_n }[/math] mit [math]\displaystyle{ a_i \in \Sigma }[/math] und [math]\displaystyle{ n \in \mathbb{N}_0 }[/math]:

[math]\displaystyle{ w = a_1 a_2 \dots a_n }[/math]

Besteht die Folge aus gar keinem Zeichen ([math]\displaystyle{ n = 0 }[/math]), heißt sie leeres Wort und wird mit dem griechischen Buchstaben [math]\displaystyle{ \varepsilon }[/math] (Epsilon) oder seltener mit [math]\displaystyle{ \lambda }[/math] (Lambda) bezeichnet.

Die Menge aller endlichen Wörter, die sich aus den Zeichen des Alphabets [math]\displaystyle{ \Sigma }[/math] bilden lassen (einschließlich des leeren Wortes [math]\displaystyle{ \varepsilon }[/math]), heißt Kleenesche Hülle [math]\displaystyle{ \Sigma^* }[/math]. Für [math]\displaystyle{ w \in \Sigma^* }[/math] liest man: „[math]\displaystyle{ w }[/math] ist ein Wort über [math]\displaystyle{ \Sigma }[/math]“. Die Menge aller Wörter ohne das leere Wort wird mit [math]\displaystyle{ \Sigma^+ = \Sigma^* \setminus \{\varepsilon\} }[/math] bezeichnet.

Eigenschaften und Operationen

Wortlänge

Die Wortlänge [math]\displaystyle{ |w| }[/math] gibt die Gesamtzahl der Zeichen an, aus denen das Wort [math]\displaystyle{ w }[/math] besteht. Kommt dasselbe Zeichen mehrfach im Wort vor, wird jedes Auftreten einzeln mitgezählt. Für ein Wort [math]\displaystyle{ w = a_1 a_2 \dots a_n }[/math] gilt [math]\displaystyle{ |w| = n }[/math].

Leeres Wort

Das leere Wort [math]\displaystyle{ \varepsilon }[/math] enthält kein einziges Zeichen, sodass für seine Wortlänge [math]\displaystyle{ |\varepsilon| = 0 }[/math] gilt. Es gehört zu jedem [math]\displaystyle{ \Sigma^* }[/math] ([math]\displaystyle{ \varepsilon \in \Sigma^* }[/math]), weil es kein Zeichen enthält, das außerhalb von [math]\displaystyle{ \Sigma }[/math] liegt. Das leere Wort selbst ist jedoch kein einzelnes Zeichen des Alphabets ([math]\displaystyle{ \varepsilon \notin \Sigma }[/math]).

Verkettung (Konkatenation)

Werden zwei Wörter [math]\displaystyle{ u \in \Sigma^* }[/math] und [math]\displaystyle{ v \in \Sigma^* }[/math] direkt hintereinander gehängt, entsteht ein neues Wort [math]\displaystyle{ uv \in \Sigma^* }[/math]. Diese Operation heißt Verkettung oder Konkatenation.

  • Additivität der Wortlänge: Die Länge des verketteten Wortes ist die Summe der Einzellängen: [math]\displaystyle{ |uv| = |u| + |v| }[/math].
  • Reihenfolge (Nicht-Kommutativität): Bei einem Wort kommt es exakt auf die Reihenfolge der Zeichen an. Im Allgemeinen sind [math]\displaystyle{ uv }[/math] und [math]\displaystyle{ vu }[/math] verschiedene Wörter ([math]\displaystyle{ uv \neq vu }[/math]).
  • Neutrales Element: Das Verketten mit dem leeren Wort [math]\displaystyle{ \varepsilon }[/math] verändert ein Wort nicht: [math]\displaystyle{ w\varepsilon = \varepsilon w = w }[/math].
  • Wortpotenz: Wird dasselbe Wort oder Zeichen [math]\displaystyle{ k }[/math]-mal hintereinander gehängt, schreibt man verkürzt [math]\displaystyle{ w^k }[/math] (wobei [math]\displaystyle{ w^0 = \varepsilon }[/math] festgelegt ist).

Wörter und formale Sprachen

Während [math]\displaystyle{ \Sigma^* }[/math] sämtliche Wörter enthält, die sich aus den Zeichen des Alphabets [math]\displaystyle{ \Sigma }[/math] bilden lassen, umfasst eine Formale Sprache [math]\displaystyle{ L \subseteq \Sigma^* }[/math] nur diejenigen Wörter, die zusätzliche formale Regeln erfüllen.

Prüft ein endlicher Automat [math]\displaystyle{ A }[/math] die Eingabewörter über [math]\displaystyle{ \Sigma }[/math], gehört ein Wort [math]\displaystyle{ w \in \Sigma^* }[/math] genau dann zur vom Automaten akzeptierten Sprache [math]\displaystyle{ L(A) }[/math], wenn sich der Automat nach dem vollständigen Lesen von [math]\displaystyle{ w }[/math] in einem Endzustand befindet. Ist bereits der Startzustand des Automaten ein Endzustand, wird auch das leere Wort [math]\displaystyle{ \varepsilon }[/math] akzeptiert ([math]\displaystyle{ \varepsilon \in L(A) }[/math]).

Beispiele

Wörter, Wortlängen und Verkettungen bestimmen

Gegeben sei das Alphabet [math]\displaystyle{ \Sigma = \{E, K\} }[/math]. Aus diesen beiden Zeichen lassen sich unter anderem folgende Wörter aus [math]\displaystyle{ \Sigma^* }[/math] bilden und untersuchen:

  • Wortlängen bestimmen:
    • Das Wort [math]\displaystyle{ w_1 = KEK }[/math] besteht aus drei Zeichen, hat also die Wortlänge [math]\displaystyle{ |KEK| = 3 }[/math].
    • Das Wort [math]\displaystyle{ w_2 = KKKK }[/math] (in Potenzschreibweise [math]\displaystyle{ K^4 }[/math]) hat die Wortlänge [math]\displaystyle{ |KKKK| = 4 }[/math].
    • Das leere Wort [math]\displaystyle{ \varepsilon }[/math] enthält kein Zeichen und besitzt die Wortlänge [math]\displaystyle{ |\varepsilon| = 0 }[/math].
  • Wörter verketten: Gegeben seien die Wörter [math]\displaystyle{ u = EK }[/math] (mit [math]\displaystyle{ |u| = 2 }[/math]) und [math]\displaystyle{ v = K }[/math] (mit [math]\displaystyle{ |v| = 1 }[/math]).
    • Das Anhängen von [math]\displaystyle{ v }[/math] an [math]\displaystyle{ u }[/math] ergibt [math]\displaystyle{ uv = EKK }[/math] mit der Länge [math]\displaystyle{ |uv| = |u| + |v| = 2 + 1 = 3 }[/math].
    • In umgekehrter Reihenfolge entsteht [math]\displaystyle{ vu = KEK }[/math]. Da die Zeichen an unterschiedlichen Positionen stehen, gilt [math]\displaystyle{ uv \neq vu }[/math].
    • Die Verkettung mit dem leeren Wort ergibt [math]\displaystyle{ u\varepsilon = EK\varepsilon = EK = u }[/math].

Akzeptierte und abgelehnte Wörter am Kaffeeautomaten unterscheiden

 
Vollständiger DEA des Kaffeeautomaten

Der abgebildete Kaffeeautomat besitzt das Eingabealphabet [math]\displaystyle{ \Sigma = \{E, K\} }[/math]. Ein Kaffee [math]\displaystyle{ K }[/math] füllt das Satzfach um 1 Einheit, ein Espresso [math]\displaystyle{ E }[/math] um 2 Einheiten. Der Automat startet im Zustand [math]\displaystyle{ q_0 }[/math] (0 Einheiten) und akzeptiert genau die Wörter, nach deren Eingabe er sich im doppelt umkreisten Endzustand [math]\displaystyle{ q_4 }[/math] (Satzfach mit genau 4 Einheiten voll) befindet:

  • Akzeptierte Wörter ([math]\displaystyle{ w \in L }[/math]): Genau fünf Wörter über [math]\displaystyle{ \Sigma }[/math] führen vom Startzustand [math]\displaystyle{ q_0 }[/math] in den Endzustand [math]\displaystyle{ q_4 }[/math] und bilden die akzeptierte Sprache:
[math]\displaystyle{ L = \{KKKK, EE, EKK, KEK, KKE\} }[/math]
  • Abgelehnte Wörter ([math]\displaystyle{ w \in \Sigma^* }[/math], aber [math]\displaystyle{ w \notin L }[/math]): Alle übrigen Wörter aus [math]\displaystyle{ \Sigma^* }[/math] sind zwar formal gültige Wörter über dem Alphabet [math]\displaystyle{ \Sigma }[/math], gehören aber nicht zur Sprache [math]\displaystyle{ L }[/math]:
    • [math]\displaystyle{ KK }[/math] ([math]\displaystyle{ |KK| = 2 }[/math]): Nach zwei Kaffees endet der Automat im Zustand [math]\displaystyle{ q_2 }[/math]. Da [math]\displaystyle{ q_2 }[/math] kein Endzustand ist, gilt [math]\displaystyle{ KK \notin L }[/math].
    • [math]\displaystyle{ EEK }[/math] ([math]\displaystyle{ |EEK| = 3 }[/math]): Nach [math]\displaystyle{ EE }[/math] ist zwar [math]\displaystyle{ q_4 }[/math] erreicht, das anschließende [math]\displaystyle{ K }[/math] führt jedoch weiter in den Fehlerzustand [math]\displaystyle{ q_5 }[/math] (Überlauf bei 5 Einheiten). Daher gilt [math]\displaystyle{ EEK \notin L }[/math].
    • [math]\displaystyle{ \varepsilon }[/math] ([math]\displaystyle{ |\varepsilon| = 0 }[/math]): Ohne Eingabe verbleibt der Automat im Startzustand [math]\displaystyle{ q_0 }[/math]. Da [math]\displaystyle{ q_0 }[/math] kein Endzustand ist, wird das leere Wort nicht akzeptiert ([math]\displaystyle{ \varepsilon \notin L }[/math]).