Wörter

Eine formalere Sicht auf Wörter

Um präziser über Wörter sprechen zu können, muss zuallererst klar sein, aus welchen Zeichen die Wörter bestehen. Hierfür brauchst du ein Alphabet.

Alphabete

Ein Alphabet ist eine endliche Menge von Buchstaben oder allgemeiner von irgendwelchen Zeichen. So besteht das Alphabet, das in Deutschland benutzt wird, aus den 26 Buchstaben von A bis Z (Umlaute einmal ausgenommen). Wenn du aber nach Griechenland reist, bemerkst du, dass sehr viele Schilder dort nicht mit diesen Zeichen geschrieben sind. Denn dort wird das griechische Alphabet mit den Zeichen $\alpha$ bis $\omega$ verwendet.

Wörter

Wenn du nun ein bestimmtes Alphabet zugrunde legst, kannst du die Buchstaben aus diesem Alphabet aneinanderreihen und daraus Wörter basteln. Ein Wort ist nämlich eine endlich lange Folge von Zeichen aus einem Alphabet. So ist zum Beispiel das Wort ESEL eine solche Folge von Buchstaben aus dem Alphabet von A bis Z.

Ein paar Grundbegriffe helfen dir, über Wörter zu reden:

• Wortlänge: Die Länge eines Wortes ist die Anzahl der Zeichen, aus denen das Wort besteht. Beispielsweise ist die Länge des Wortes ESEL gleich 4. Die Schreibweise für die Länge eines Wortes $w$ ist $|w|$.

• Verkettung: Du kannst Wörter miteinander verketten, das bedeutet einfach hintereinanderhängen (manchmal findest du auch den Begriff konkatenieren dafür). Wenn du zum Beispiel die Wörter APFEL und MUS verkettest, erhältst du APFELMUS. Du schreibst dafür APFEL $\circ$ MUS = APFELMUS. Dabei musst du die Reihenfolge beachten, denn es gilt MUS $\circ$ APFEL = MUSAPFEL. Der Kringel $\circ$ steht hierbei für die Operation des Verkettens von Wörtern; er wird manchmal auch weggelassen (wie das Mal-Zeichen bei der Multiplikation von Zahlen). Ein wichtiger Sonderfall der Verkettung ist die Potenz: die Verkettung eines Wortes mit sich selbst. Wenn du ein Wort $w$ zum Beispiel dreimal mit sich selbst verkettest, also $w\ \circ\ w\ \circ\ w$ bildest, schreibst du das als $w^3$. So ist zum Beispiel (BLA)$^3$ = BLABLABLA. Aber Achtung: Wenn du die Klammern weglässt, kommt BLA$^3$ = BLAAA heraus!

• Das leere Wort: Genauso wie die 1 in der Arithmetik eine sehr wichtige Zahl ist, spielt in den formalen Sprachen das leere Wort eine wichtige Rolle. Du schreibst es mit dem griechischen Buchstaben $\varepsilon$ . Die wichtigsten Eigenschaften des leeren Wortes sind, dass $|\varepsilon| = 0$ ist und dass $\varepsilon \circ w = w \circ \varepsilon = w$ gilt (das heißt wenn du ein Wort mit $\varepsilon$ verkettest, bleibt es wie es war). Und außerdem gilt für jedes beliebige Wort $w$, dass $w^0=\varepsilon$ ist (ein Wort 0-mal mit sich selbst verkettet ergibt $\varepsilon$, genauso wie in der Arithmetik für jede beliebige Zahl $x$ gilt, dass $x^ 0 = 1$ ist).

Wörter und Sprachen

Wenn du nun dein Wissen über Alphabete und Wörter zusammenwirfst, kannst du auch Dinge definieren wie die Menge aller Wörter der Länge $n$ über einem Alphabet $A$.

Wenn du zum Beispiel das Alphabet $A = \{$a, b$\}$ zugrunde legst, dann ist die Menge der Wörter der Länge 2, die du damit bilden kannst, gleich $\{$aa, ab, ba, bb$\}$. Die Menge der Wörter der Länge 1 ist $\{$a, b$\}$. Und die Menge der Wörter der Länge 0 ist $\{ \varepsilon \}$.

Allgemein bezeichnet man die Menge der Wörter der Länge $n$ über einem Alphabet $A$ als $A^n$. Und die Menge aller Wörter, egal welcher Länge, über dem Alphabet $A$ bezeichnet man mit $A^*$.

Und nun kommt das Verrückte: Jede beliebige Teilmenge von $A^*$ wird als eine Sprache über $A$ bezeichnet. Eine Sprache über einem Alphabet $A$ ist also eine Menge von irgendwelchen Wörtern über $A$. Ob du es glaubst oder nicht, aber $\{$XBFT, UTVQWW, TJJ$\}$ ist eine Sprache über dem Alphabet von A bis Z. Es kommt also überhaupt nicht darauf an, ob die Wörter der Sprache irgendeine bestimmte Form haben, ob sie etwas bedeuten, ob du sie aussprechen kannst. Es müssen nur Wörter über dem Alphabet $A$ sein. Doch dazu im nächsten Abschnitt über Sprachen mehr.

Anwendung an Beispielen

• Sei $A = \{$a, b, c$\}$, dann ist $A^2 = \{$aa, ab, ac, ba, bb, bc, ca, cb, cc$\}$.

• Es gilt $\varepsilon^n = \varepsilon$

• Wenn $A$ ein Alphabet ist, so gilt $|A^n| = |A|^n$. Was bedeutet das? Die Anzahl der Wörter der Länge $n$ ist gleich der Anzahl der Alphabetzeichen hoch $n$ (die Betragsstriche bedeuten bei Mengen die Anzahl ihrer Elemente).

• Wenn Satzzeichen und das Leerzeichen zum Alphabet $A$ dazugehören, dann ist auch ein Gebilde, das du umgangssprachlich als Satz bezeichnen würdest, ein Wort über $A$. Und sogar ein ganzer Text, der aus vielen Sätzen besteht, ist ein Wort, nämlich eine endlich lange Folge von Alphabetzeichen.