In dieser Unit führen wir die grundlegenden Begriffe von Formalen Sprachen ein, die dann in der Arbeit mit Automaten und Grammatiken Verwendung finden. Formale Sprachen stammen als Konzept ursprünglich aus der Linguistik, werden aber insbesondere in der Informatik viel eingesetzt. Man nutzt sie zum Beispiel in der Berechenbarkeitstheorie und für Compilerbau und Programmverifikation, natürlich in Stringalgorithmen aber auch in der prozeduralen Generierung von 3D-Modellen.

Alphabete und Wörter

Die kleinsten Bausteine von Formalen Sprachen sind Symbole. In unseren Beispielen sind dies oftmals lateinische Buchstaben oder arabische Ziffern. Symbole könnten aber auch beliebige andere Konstrukte sein: Zeichen anderer Schriften, natürlichsprachliche Worte, Bilder, ... - beliebige Objekte eben. Eine endliche, nichtleere Menge von Symbolen nennen wir Alphabet. Sei \(\Sigma\) ein solches Alphabet. Eine endliche Abfolge von Symbolen aus \(\Sigma\) wird als Wort über \(\Sigma\) bezeichnet. Die Menge aller Wörter über \(\Sigma\) notieren wir als \(\Sigma^*\). Eine spezielle Rolle nimmt dabei das sogenannte leere Wort \(\varepsilon\) ein, das aus keinen Symbolen besteht.

Aus den Symbolen des Alphabets \(\Sigma = \{ a, b \}\) können wir zum Beispiel das Wort \(bba\) der Länge 3, das Wort \(a\) der Länge 1 oder auch das leere Wort (repräsentiert durch \(\varepsilon\)) der Länge 0 bilden.

Für zwei Worte \(u, w \in \Sigma^*\) schreiben wir \(uw\) für die Konkatenation (Verkettung) aller Symbole aus \(u\) mit allen Symbolen aus \(w\). Nehmen wir  also beispielsweise die Wörter \(u = ab\) und \(w = ba\), dann ist deren Konkatenation \(uw = abba\).

Für jedes Wort \(w \in \Sigma^*\) schreiben wir \(|w|\) für die Länge von \(w\), die als Anzahl der (nicht zwingend unterschiedlichen) Symbole in \(w\) definiert ist. Davon abgeleitet bezeichnet, für ein Symbol \(x \in \Sigma\), der Ausdruck \(|w|_x\) die Anzahl der Vorkommen von \(x\) in \(w\). Für ein \(i \in \mathbb{N}\) und ein Symbol \(x\) schreiben wir \(x^i\) und meinen damit die Zeichenkette, die aus \(i\) Wiederholungen des Symbols \(x\) besteht.

Ein Beispiel: Sei \(\Sigma = \{a, b\}\). Dann sind \(a\) und \(b\) die Symbole von \(\Sigma\). Die Menge aller Wörter über dem Alphabet ist \(\Sigma^* = \{\varepsilon, a, b, aa, ab, ba, bb, aaa, \ldots \}\). Exemplarische Wortlängen sind \(|aba| = 3\), \(|\varepsilon| = 0\) und \(|a| = 1\). Es gilt außerdem \(|aba|_a = 2\) und \(b^5 = bbbbb\).

Sprachen

Für ein gegebenes Alphabet \(\Sigma\) heißt jede Teilmenge \(L \subseteq \Sigma^*\) Sprache, eine Sprache ist also einfach eine Menge von Wörtern über einem Alphabet. Das Komplement einer Sprache \(L\) ist definiert als \(\overline{L} = \Sigma^* \setminus L\). Wenn zu einer Sprache kein Alphabet angegeben ist gehen wir davon aus, dass dieses aus genau den in der Sprache benutzten Symbolen besteht.

Um Sprachen anzugeben bedienen wir uns ganz normaler Mengenschreibweise, zum Beispiel sind folgende Mengen Sprachen über \(\Sigma = \{a, b\}\):

• \(L_1 = \{a, ab, aabb\}\)
• \(L_2 = \{ a^nb^n \mid n \in \mathbb{N}\}\)
• \(L_3 = L_1 \cup L_2\)
• \(L_4 = \{ w \in \Sigma^* \mid w \text{ endet auf } b \}\)

Interessant ist für uns dabei insbesondere die Konkatenation von Sprachen und der davon abgeleitete Kleene'sche Abschluss (benannt nach Stephen Cole Kleene): Für zwei Sprachen \(L_1, L_2\) ist die Konkatenation der beiden Sprachen definiert als \(L_1 \cdot L_2 = \{w_1w_2 \mid w_1 \in L_1, w_2 \in L_2\}\). Induktiv definieren wir damit den Kleene'schen Abschluss einer Sprache \(L\); dieser bezeichnet die Menge \(L^*\) aller Verkettungen von endlich vielen Wörtern der Sprache:

• \(L^0 = \{\varepsilon\}\)
• \(\forall k > 0 \colon L^k = L^{k-1} \cdot L\)
• \(L^* = \bigcup_{k \in \mathbb{N}} L^k\)
• analog gilt \(L^+ = \bigcup_{k \in \mathbb{N}\setminus\{0\}} L^k = L^* \cdot L\)

Die Menge \(\Sigma^*\) aller Wörter über einem Alphabet \(\Sigma\) ist eigentlich genauso definiert - als Kleene'scher Abschluss über dem Alphabet. Als Kurzschreibweise definiert man dazu gerne noch \(\Sigma^+ = \Sigma^* \cdot \Sigma\).

Was haben wir gelernt?

• Formale Sprachen sind Mengen von Wörtern über einem Alphabet von Symbolen.
• Wir verwenden spezielle Notationen für das leere Wort \(\varepsilon\), Konkatenationen und Wortlängen sowie den Kleene'schen Abschluss.

Im Folgenden werden wir Sprachen häufig über die Berechnungsmodelle charakterisieren, mit denen sie entschieden werden können; zum Beispiel mittels Endlicher Automaten.