Du hast mit Sicherheit ein sehr allgemeines Verständnis von Wörtern und dieses Verständnis ist in den meisten Fällen korrekt. Aber um mathematisch mit Wörtern umzugehen und diese beispielsweise in Algorithmen zu verwenden ist es nötig den Begriff des Wortes zu formalisieren.

Eine formalere Sicht auf Wörter und Alphabete

Um präziser über Wörter sprechen zu können, muss man zuallererst festlegen, welche Zeichenfolgen einem Wort entsprechen und welche nicht. Hierfür dienen hauptsächlich sogenannte Alphabete

Alphabete

Alphabete sind Mengen von Buchstaben. So besteht das Alphabet das in Deutschland benutzt wird aus den Buchstaben von A bis Z. Wenn man aber nach Griechenland reist wird man feststellen müssen, dass sehr viele Schilder dort nicht mit diesen Zeichen geschrieben sind. Denn dort wird ein anderes Alphabet benutzt, nämlich das griechische Alphabet mit den Zeichen α\alpha bis ω\omega.

Wörtern

Hat man nun also ein Alphabet definiert, kann man sich aus Buchstaben aus diesem Alphabet Wörter basteln. Und damit kann man dann zum Beispiel formale Sprachen definieren. Dafür gibts es erstmal drei Grundbegriffe die du kennen solltest.

  • Wortlänge: Die Länge eines Wortes nennt man, wie in der Mengenlehre den Betrag des Wortes und schreibt dafür w|w|.
  • Konkatenation: Man kann Wörter konkatenieren. Das klingt kompliziert, bezeichnet aber einfach das Aneinanderhängen von Wörtern. Nimmt man zum Beispiel die Wörter ApfelApfel und MusMus und konkateniert sie, schreibt man das als ApfelMus=ApfelMusApfel\circ Mus=ApfelMus. Der Kringel \circ steht hierbei für die Operation des Aneinanderhängens der Zeichenketten ApfelApfel und MusMus. Dabei ist die Reihenfolge zu beachten, es gilt nämlich MusApfel=MusApfelMus\circ Apfel=MusApfel. Ein wichtiger Sonderfall von Konkatenation ist die Potenz: die Konkatenation eines Wortes mit sich selbst. Wenn wir zum Beispiel eine Wort ww drei mal mit sich selbst konkatenieren schreiben wir das als w3w^3. Dann ist zum Beispiel (Du)3=DuDuDu\left(Du\right)^3=DuDuDu. Achtung: Wenn man die Klammern weglässt kommt Du3=DuuuDu^3=Duuu raus! Im allgemeinen gilt, dass das kk-malige konkatenieren eines Wortes ww mit sich selbst geschrieben wird als wkw^k.
  • Das leere Wort: Genauso wie die 0 in der Mathematik ein sehr wichtiges Element ist, wird für formale Sprachen das leere Wort eine wichtige Rolle spielen. Man schreibt es mit dem griechischen Buchstaben ϵ\epsilon . Die wichtigsten Eigenschaften des leeren Wortes sind, dass ϵ=0|\epsilon| = 0 und das wϵ=ww \circ \epsilon = w (das heißt wenn man ein Wort mit ϵ\epsilon konkateniert bleibt es wie es war).

Wörter und Alphabete

Wenn man nun das Wissen über Wörter und Alphabete zusammenwirft kann man auch Dinge wie die Menge der Wörter der Länge n über einem Alphabet AA definieren. Sei zum Beispiel A={a,b}A = \{a,b\}. Dann ist die Wörter der Länge 0 die man damit bilden kann einfach ϵ\epsilon. Ein anderes Beispiel ist die Menge der Wörter über AA der Länge 2, die ist {aa,ab,ba,bb}\{aa,ab,ba,bb\}. Im allgemeinen bezeichnen wir die Wörter de Länge n über einem Alphabet AA als AnA^n.

Anwendung am Beispiel

  • Es gilt Beispielsweise: ϵn=ϵ\epsilon ^n = \epsilon
  • Man kann auch versuchen, ein Wort in die Konkatenation einzelner Buchstaben aufzuteilen. Beispielsweise: See=Se²See = S \circ e² . Wichtig ist hier, dass du nicht ϵ\epsilon und ee verwechselst.
  • Sei A={a,b,c}A = \{a,b,c\}, dann ist A2={ab,ac,bc,aa,bb,cc,ba,ca,cb}A^2 = \{ab,ac,bc,aa,bb,cc,ba,ca,cb\}.
Kommentieren Kommentare