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 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

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\epsilon=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