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 erstmal3 Grundbegriffe die du kenne solltest.

  • Wortlänge: Die Länge eines Wortes nennt man, wie in der Mengenlehre den Betrag des Wortes und schreib dafür %%|w|%%.

  • Konkatenation: Man kann Wörter konkatenieren. Das klingt auf den ersten Blick gefährlich, ist aber auf den zweiten Blick das einfach aneinanderhängen von Wörtern. Nimmt man zum Beispiel die Wörter %%Apfel%% und %%Mus%% und konkateniert sie, schreibt man das als %%Apfel\circ Mus = Apfelmus%%. Der %%\circ%% steht hierbei für die Operation des anhängens von %%Apfel%% an %%Mus%%. Ein wichtiger Sonderfall von Konkatenation ist die Konkatenation eines Wortes mit sich selbst. Wenn wir zum Beispiel eine Wort %%w%% 3 mal mit sich selbst konkatenieren schreiben wir das als %%w ^3%%. Dann ist zum Beispiel %%Du^2 = Du \circ Du = DuDu%%. Im allgemeinen gilt, dass das k-malig konkatenieren eines Wortes %%w%% mi sich selbst ausgeschrieben wird als %%w^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 %%|\epsilon| = 0%% und das %%w \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 %%A%% definieren. Sei zum Beispiel %%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 %%A%% der Länge 2, die ist %%\{aa,ab,ba,bb\}%%. Im allgemeinen bezeichnen wir die Wörter de Länge n über einem Alphabet %%A%% als %%A^n%%.

Anwendung am Beispiel

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