Springe zum Inhalt oder Footer
SerloDie freie Lernplattform

Wörter

Du hast mit Sicherheit ein intuitives Verständnis von Wörtern und dieses Verständnis ist in den meisten Fällen auch korrekt. Aber um mathematisch mit Wörtern umzugehen, ist es nötig, den Begriff des Wortes zu formalisieren.

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 ww ist w|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 ww zum Beispiel dreimal mit sich selbst verkettest, also w  w  ww\ \circ\ w\ \circ\ w bildest, schreibst du das als w3w^3. So ist zum Beispiel (BLA)3^3 = BLABLABLA. Aber Achtung: Wenn du die Klammern weglässt, kommt BLA3^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 ε=0|\varepsilon| = 0 ist und dass εw=wε=w\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 ww, dass w0=εw^0=\varepsilon ist (ein Wort 0-mal mit sich selbst verkettet ergibt ε\varepsilon, genauso wie in der Arithmetik für jede beliebige Zahl xx gilt, dass x0=1x^ 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 nn über einem Alphabet AA.

Wenn du zum Beispiel das Alphabet A={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 nn über einem Alphabet AA als AnA^n. Und die Menge aller Wörter, egal welcher Länge, über dem Alphabet AA bezeichnet man mit AA^*.

Und nun kommt das Verrückte: Jede beliebige Teilmenge von AA^* wird als eine Sprache über AA bezeichnet. Eine Sprache über einem Alphabet AA ist also eine Menge von irgendwelchen Wörtern über AA. 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 AA sein. Doch dazu im nächsten Abschnitt über Sprachen mehr.

Anwendung an Beispielen

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

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

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

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


Dieses Werk steht unter der freien Lizenz
CC BY-SA 4.0Was bedeutet das?