Grundbegriffe

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.

Als Wort über einer Sprache $\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