Formale Sprachen

Der Begriff formale Sprache deutet darauf hin, dass es zunächst nur auf die formalen Aspekte der Sprache ankommt. Mit den Wörtern der Sprache werden zunächst keine Bedeutungen verbunden – dies kommt erst später hinzu, zum Beispiel bei Programmiersprachen.

Auch natürliche Sprachen wie Deutsch, Englisch oder Latein sind nach bestimmten Regeln aufgebaut, nämlich nach einer Grammatik. Diese Regeln sind allerdings sehr kompliziert und mit zahlreichen Ausnahmen verbunden. Formale Sprachen in der Informatik, auch Programmiersprachen, sind dagegen nach sehr viel einfacheren Regeln aufgebaut. Auch hier wird die Gesamtheit dieser Regeln als Grammatik bezeichnet.

Definition

Eine formale Sprache $L$ über einem Alphabet $A$ ist eine beliebige Teilmenge $L \subseteq A^*$. Dabei steht $A^*$ für die Menge aller Wörter, die mit den Zeichen aus dem Alphabet $A$ gebildet werden können.

Eine mögliche Sprache über dem Alphabet $A$ = {a, b} ist beispielsweise die Sprache $L$ = {a, ab, abbba}

• Wieso ist $L$ eine Sprache? Nun, $L$ ist eine Menge von gewissen Wörtern über dem Alphabet $A$ und damit eine Sprache.

• Warum besteht die Sprache $L$ ausgerechnet aus diesen Wörtern? Es gibt keinen Grund dafür. Diese Sprache ist nicht nach irgendwelchen Regeln aufgebaut.

• Was bedeuten die Wörter der Sprache? Nichts, denn mit den Wörtern einer formalen Sprache werden keine Bedeutungen verbunden.

Die Sprache $L$ aus dem obigen Beispiel besteht nur aus drei Wörtern, sie ist damit eine endliche Sprache, es gilt $|L| = 3$. Interessanter sind unendliche Sprachen, also Sprachen, die aus unendlich vielen Wörtern bestehen, so zum Beispiel folgende Sprache, nennen wir sie $L'$, über dem Alphabet $A$ = {a, b}:

$L'$ = {a, aa, aaa, aba, aaaa, aaba, abaa, abba, aaaaa, aaaba, ...}

Wie geht es bei … weiter? Dies kann niemand wissen, es kann beliebig weitergehen. Um eine unendliche Sprache genau anzugeben, ist irgendeine Art von endlicher Beschreibung dieser Sprache erforderlich.

Dies kann eine informelle Beschreibung sein, wie etwa: "Die Sprache $L'$ besteht aus allen Wörtern über $A$, die mit a anfangen und mit a aufhören."

Besser ist aber eine irgendwie geartete formale Beschreibung. In der theoretischen Informatik sind drei verschiedene Möglichkeiten üblich, um die unendliche Sprache $L'$ mit endlichen Mitteln zu beschreiben:

• durch einen regulären Ausdruck

• durch einen Automaten, der genau diese Sprache erkennt

• durch eine Grammatik, die diese Sprache erzeugt

Wieso drei verschiedene Möglichkeiten genügt nicht eine? Nun, im Prinzip ja, zum Beispiel die Grammatik. Oder der Automat. Grammatiken und Automaten verhalten sich gewissermaßen dual zueinander: Die Grammatik erzeugt eine Sprache, der Automat erkennt eine Sprache.

Mit regulären Ausdrücken lassen sich dagegen lediglich sehr einfach aufgebaute Sprachen beschreiben, wie etwa die obige Sprache $L'$. Ein regulärer Ausdruck ist gewissermaßen ein Muster, nach welchem alle Wörter der Sprache aufgebaut sind.

Du findest Methoden zum Arbeiten mit regulären Ausdrücken in Programmiersprachen wie Java, Python, JavaScript, PHP, …

Zu regulären Ausdrücken gleich mehr. Zuerst lernst du die Operationen kennen, die du brauchst, um reguläre Ausdrücke zu bilden.