Wort (theoretische Informatik)

Grundbegriff und Definition

In der theoretischen Informatik ist ein Wort eine endliche Folge von Symbolen eines Alphabets Σ. Es bezeichnet dabei lediglich eine Zeichenkette, nicht eine mögliche Bedeutung wie in der natürlichen Sprache. Wörter sind die Elemente formaler Sprachen und dienen unter anderem der mathematischen Modellierung, der Theorie der Programmiersprachen und der Berechenbarkeitstheorie.

Ein Wort w der Länge n ist eine Folge (x₁, x₂, …, xₙ) mit xᵢ ∈ Σ für alle i ∈ {1, …, n}. Dabei ist n eine natürliche Zahl einschließlich 0: ℕ₀ = {0, 1, 2, …}. Die Länge wird mit |w| bezeichnet; |w|ₓ gibt an, wie oft das Zeichen x in w vorkommt.

Das leere Wort ε besteht aus keinem Symbol und hat die Länge 0. Gelegentlich wird es auch mit Λ bezeichnet. Die Menge aller Wörter über Σ ist die Kleenesche Hülle Σ*:

Σ* := ⋃ₙ∈ℕ∪{0} Σⁿ.

Die Menge der nichtleeren Wörter heißt positive Hülle:

Σ⁺ := Σ* \ {ε} = ⋃ₙ∈ℕ Σⁿ.

Häufig wird ein Wort verkürzt als w = x₁x₂…xₙ geschrieben. Diese Schreibweise ist nur eindeutig, wenn die verwendeten Symbole klar voneinander unterscheidbar sind. Beim Alphabet Σ = {a, aa} kann beispielsweise w = aaa die Folge (a, aa), (aa, a) oder (a, a, a) bedeuten. Ein Wort der Länge n kann sowohl als endliche Folge beziehungsweise Sequenz als auch als Element des n-fachen kartesischen Produkts aufgefasst werden.

Beispiele für Wörter

Für das Alphabet Σ₁ der lateinischen Buchstaben sind w₁ = haus und w₂ = xyzzy Wörter. Für das Alphabet Σ₂ = {♦, ♥, ♠, ♣} ist w₃ = ♥♣♣♥♠ ein Wort. Ihre Längen sind |w₁| = 4 und |w₂| = |w₃| = 5.

Konkatenation und ihre Eigenschaften

Die Konkatenation oder Verkettung verbindet zwei Wörter, indem ihre Symbolfolgen aneinandergereiht werden. Für x = (x₁, …, xₙ) und y = (y₁, …, yₖ) gilt:

xy = x ◦ y := (x₁, x₂, …, xₙ, y₁, y₂, …, yₖ).

Das erste Wort x ist dabei ein Präfix und das zweite Wort y ein Suffix des entstandenen Wortes. Die Länge und die absolute Häufigkeit eines Zeichens addieren sich:

|u ◦ v| = |u| + |v|,

|u ◦ v|ₓ = |u|ₓ + |v|ₓ.

Das leere Wort ε ist das neutrale Element, denn für jedes Wort w gilt w ◦ ε = ε ◦ w = w. Die Konkatenation ist außerdem assoziativ. Deshalb bildet (Σ*, ◦, ε) ein Monoid: Klammern dürfen weggelassen werden, weil (u ◦ v) ◦ z = u ◦ (v ◦ z) gilt.

Kommutativ ist die Konkatenation dagegen nicht. Im Allgemeinen gilt also u ◦ v ≠ v ◦ u. Beispielsweise ist haus ◦ ♥♣♣♥♠ = haus♥♣♣♥♠, während ♥♣♣♥♠ ◦ haus = ♥♣♣♥♠haus ergibt.

Potenzen von Wörtern

Die n-te Potenz wⁿ ist die n-fache Wiederholung eines Wortes durch Konkatenation. Rekursiv ist sie definiert durch:

w⁰ := ε,

wⁿ⁺¹ := wⁿ ◦ w für n ∈ ℕ₀.

Damit gilt zum Beispiel (xyzzy)⁰ = ε, (♥♣♣♥♠)¹ = ♥♣♣♥♠ und (haus)³ = haushaushaus.

Für jedes Wort w gelten die Formeln

|wⁿ| = n · |w|

und für jedes Zeichen x:

|wⁿ|ₓ = n · |w|ₓ.

Spiegelung und Palindrome

Die Spiegelung oder das Reverse eines Wortes w wird mit wᴿ bezeichnet und entsteht durch Rückwärtslesen. Ist w = (x₁, x₂, …, xₙ), dann ist wᴿ = (y₁, y₂, …, yₖ) mit k = n und yᵢ = xₙ₊₁₋ᵢ für alle i ∈ {1, …, k}. Die Länge bleibt erhalten: |wᴿ| = |w|.

Beispiele sind εᴿ = ε, (abb)ᴿ = bba und (♥♣♠♥)ᴿ = ♥♠♣♥.

Eine rekursive Definition lautet: εᴿ := ε. Ist w = v ◦ a mit v ∈ Σ* und a ∈ Σ, dann gilt wᴿ := a ◦ vᴿ. So ergibt sich etwa (abb)ᴿ = b ◦ (ab)ᴿ = bba.

Ein Wort wie abaaba, das mit seiner Spiegelung identisch ist, heißt Palindrom. Mathematisch sind Palindrome die Fixpunkte der Spiegelung w ↦ wᴿ.

Infixe, Präfixe und Suffixe

Ein Infix, auch Teilwort oder Faktor, ist eine zusammenhängende Folge aufeinanderfolgender Symbole eines Wortes. Ein Wort u ist genau dann Infix von w, wenn es Wörter p und s aus Σ* gibt, sodass p ◦ u ◦ s = w gilt. Das leere Wort ist Infix jedes Wortes; außerdem ist jedes Wort Infix von sich selbst. Ein Infix, das nicht mit dem gesamten Wort identisch ist, heißt echtes Infix. In vielen Computersprachen wird dafür die englische Bezeichnung substring verwendet.

Beispielsweise ist aba ein Infix von babaab, abaababb und aba, aber nicht von abba, babbaabbab oder ε.

Ein Präfix ist ein Infix am Anfang eines Wortes. Es gilt:

u ist Präfix von w genau dann, wenn ∃s ∈ Σ*: u ◦ s = w.

Auch das leere Wort ist Präfix jedes Wortes, und jedes Wort ist Präfix von sich selbst. Ein nicht mit dem ganzen Wort identisches Präfix heißt echtes Präfix. Für w = abaabb lauten die echten Präfixe ε, a, ab, aba, abaa und abaab.

Ein Suffix, auch Postfix, ist ein Infix am Ende eines Wortes. Es gilt:

u ist Suffix von w genau dann, wenn ∃p ∈ Σ*: p ◦ u = w.

Das leere Wort ist Suffix jedes Wortes, und jedes Wort ist Suffix von sich selbst. Ein nicht identisches Suffix heißt echtes Suffix. Für w = abaabb sind die echten Suffixe baabb, aabb, abb, bb, b und ε.