Grundbegriffe

Alphabet

Als Alphabet bezeichnet man eine Menge von Zeichen. Eine Menge als "Alphabet" zu bezeichnen sagt nichts über diese Menge aus, sondern gibt an, was man vorhat mit der Menge zu tun.

Beispiele:

• Das Alphabet für Unalzahlen $\{1\}$
• Das Alphabet der Dualstellen $\{0,1\}$
• Ein Alphabet für einfache mathematische Formeln $\{+,-,\cdot,\div, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$
• TODO

In den meisten Fällen verwenden wir endliche Alphabete. Es ist aber ohne Weiteres möglich, eine unendliche Menge als Alphabet zu benutzen.

Wort

Als Wort über einem Alphabet $\cal L$ bezeichnet man eine endliche Folge von Zeichen aus $\cal L$. Die Menge der Wörter über einer Sprache $\cal L$ bezeichnen wir mit ${\cal L}^*$. Manchmal spricht man auch von Zeichenketten oder Strings.

Beispiele:

• Die Wörter über $\{1\}$ sind endliche Folgen von Einsen; sie stellen die Unaldarstellungen von $\mathbb{N}$ dar.
• $00101001$, $1$, $000$ sind Wörter über $\{0,1\}$
• $(1+(2\cdot 3))$, aber auch syntaktisch falsche Wörter wie $)($, sind Wörter über $\{+,-,\cdot,\div, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$
• Das leere Wort, das aus genau $0$ Zeichen besteht, ist Wort über jeder Sprache. Es wird in der Literatur oft als $\varepsilon$ bezeichnet. Die Menge der nichtleeren Wörter über einer Sprache $\cal L$ bezeichnet man mit ${\cal L}^+ := {\cal L}^*\backslash\{\varepsilon\}$.
• TODO

Gegeben zwei Wörter $a$ und $b$, kann man sie aneinanderhängen; man schreibt dafür $ab$, oder manchmal $a*b$, und bezeichnet dies als Verkettung oder Konkatenation. Beispielsweise ist $a\varepsilon=a$ für alle Wörter $a$, und die Wörter $bla$ und $blubb$ ergeben konkateniert das Wort $blablubb$.

Sprache

Als Sprache über einem Alphabet $\cal L$ bezeichnet man eine (nicht notwendigerweise endliche) Teilmenge von ${\cal L}^*$.

Beispiele:

• Die leere Sprache $\emptyset$ ist Sprache über jedem Alphabet.
• ${\cal L}^+$ und ${\cal L}^*$ sind Sprachen über dem Alphabet $\cal L$.
• Die Menge der syntaktisch korrekten Formeln über $\{+,-,\cdot,\div, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ ist eine Sprache. Sie enthält insbesondere zum Beispiel nicht die Zeichenkette $)($.
• Die Menge der unalen Primzahlen $\{11, 111, 11111, 1111111, 11111111111, 1111111111111, \ldots\}$ ist eine Sprache über $\{1\}$.
• TODO

Codierung als Zahlen

Ist ein endliches Alphabet $\cal L$ mit $n$ Zeichen gegeben, so kann man jedem Zeichen eineindeutig eine natürliche Zahl aus $[1;n]$ zuordnen. Hat man so eine Zuordnung $g:{\cal L}\rightarrow [1;n]\cap\mathbb{N}$ getroffen, und ein Wort $a_0a_1\ldots a_{k-1}$ gegeben, wobei alle $a_i\in{\cal L}$ Zeichen sind, dann kann man diesem Wort die Zahl $\sum\limits_{i=0}^{k-1} n^i\cdot g(a_i)$ zuordnen. $\varepsilon$ wird $0$ zugeordnet.

Lemma: Diese Zuordnung ist Bijektiv. Beweis: Übung.

Beispiel: Betrachten wir wieder das Alphabet $\{+,-,\cdot,\div, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$. Es enthält 16 Zeichen. Betrachten wir nun die Zuordnung $+\rightarrow 1$, $-\rightarrow 2$,$\cdot\rightarrow 3$,$\div\rightarrow 4$,$(\rightarrow 5$,$)\rightarrow 6$,$0\rightarrow 7$,$1\rightarrow 8$,$2\rightarrow 9$,$3\rightarrow 10$,$4\rightarrow 11$,$5\rightarrow 12$,$6\rightarrow 13$,$7\rightarrow 14$,$8\rightarrow 15$,$9\rightarrow 16\}$.

Das Wort $)($ bekäme die Zahl $6+ 5 \cdot 16=86$ zugeordnet, das Wort $(1+(2\cdot 3))$ bekäme die Zahl $16^8\cdot 5+ 16^7\cdot 8 + 16^6\cdot 1 + 16^5\cdot 5+ 16^4\cdot 9 + 16^3\cdot 3 + 16^2\cdot 10+16\cdot 6+6 = 23661722118$ zugeordnet.

Da es so einfach ist, Wörter auf Zahlen eineindeutig abzubilden, werden viele Begriffe, die wir im Kurs einführen, in der Literatur oft nur über natürlichen Zahlen eingeführt. Die Begriffe sind dann auf triviale Weise äquivalent.