Formale Sprachen

Alles Wichtige über formale Sprachen! Nach der allgemeinen Erläuterung gibt es alle Operationen auf formale Sprachen als Überblick. Danach wird die Konkatenation von Sprachen und die Kleenesche Hülle ausführlich erklärt.

Formale Sprache

Formale Sprachen sind künstliche Sprachen, die es Computern ermöglichen, Daten und Informationen zu verarbeiten. Oft werden diese formalen Sprachen von endlichen Automaten verwaltet. Eine formale Sprache L besteht aus einer Menge von Wörtern, die wiederum aus Zeichen des Alphabets der Sprache bestehen. Das Alphabet  ist hierbei die Menge der Zeichen, die in einem Wort  benutzt werden dürfen, wie zum Beispiel die Buchstaben von A bis Z und Umlaute im deutschen Alphabet.

direkt ins Video springen

Bei Sprachen gilt es allgemein zwischen Syntax und Semantik zu unterscheiden. Unter der Syntax versteht man hierbei die Regeln, mit denen Wörter der Sprache aufgebaut werden und unter der Semantik die Bedeutung dieser Wörter. Dieser Satz beispielsweise ist zwar syntaktisch richtig, ergibt aber eventuell überhaupt keinen Sinn: „Eine Blume kocht flüssige Uhren“. Nur durch das Zusammenspiel von Syntax und Semantik kann eine Sprache funktionieren.

Um für den Computer verständlich zu sein, haben formale Sprachen zwar teilweise Ähnlichkeiten mit gesprochenen Sprachen, unterscheiden sich aber stark durch eine mathematische und logische Notation und Formulierung.

Operationen auf formale Sprachen

Auf formale Sprachen können auch Mengenoperationen angewandt werden. Gegeben seien dabei beispielsweise die zwei Sprachen L₁ und L₂ . Auf die Mengen der Wörter der beiden Sprachen kann man nun die Vereinigungs-, Schnitt- oder Differenzmenge bilden.

• Vereinigungsmenge:
• Durchschnittsmenge:
• Differenzmenge: 

Hierbei ergibt sich für das Alphabet bei allen Operationen die Vereinigungsmenge der beiden Alphabete   und , da alle Zeichen beider Sprachen in der neu entstandenen Sprache vorkommen können.

Mengenoperationen

• Vereinigungsmenge: In einer Vereinigung zweier Mengen sind alle Elemente, die in mindestens einer der beiden Mengen vorkommen.
• Durchschnittsmenge: Der Durchschnitt von zwei Mengen A und B ergibt genau die Elemente, die sowohl in A, als auch in B sind.
• Differenzmenge: Zu guter Letzt die Differenz. Die Differenz aus den Mengen A und B ergibt genau die Elemente, die zwar in A, nicht aber in B sind.

direkt ins Video springen

Konkatenation

Ein sehr wichtiges Element formaler Sprachen ist die Konkatenation. Darunter versteht man eine Verkettung von Zeichen oder Zeichenketten. Die Konkatenation von zwei formalen Sprachen L₁ und L₂ ergibt eine neue formale Sprache, die alle möglichen Aneinanderreihungen der Wörter u und v aus den Sprachen L₁ und L₂ enthält. Dabei stellt_, u ein Element der Sprache L₁, und v ein Element der Sprache L₂ dar.

Konkatenation Beispiel

Als Beispiel soll dabei ein Alphabet zweier Sprachen aus den Buchstaben „a“ und „e“ bestehen:

Die Sprache L₁ besteht aus den Wörtern „aa“ und „ee“, die Sprache L₂ hingegen aus den Wörtern „ae“ und „ea“.

Die Sprachen L₁ und L₂ sollen konkateniert werden. Die neue Sprache enthält alle Wörter, die mit einem Wort aus L₁ beginnen und auf ein Wort aus L₂ enden.

Wichtig zu wissen ist außerdem, dass eine Konkatenation eines Wortes  mit der leeren Menge  das Wort unverändert zurückgibt, also:

Potenz

Weiter geht es mit der Potenz. Diese erhält man einfach durch n-fache Konkatenation eines Wortes mit sich selbst.

Ein Wort  mit der Potenz 4 wird also vervierfacht:

Nun das Gleiche mit der Sprache L zur Potenz 2: L = {a, e}. Nun muss jedes Element der Sprache L mit einem beliebigen Element der gleichen Sprache verbunden werden. Wenn man dabei jede Möglichkeit durchspielt, kommt man auf das folgende Ergebnis:

Ist die Potenz einer Sprache oder eines Wortes 0, so erhalten wir immer die leere Menge:

Außerdem ergibt die leere Menge potenziert ebenfalls die leere Menge:

Kleenesche Hülle

Die kleenesche Hülle eines Alphabets oder einer formalen Sprache L ist die Menge, die durch beliebige Konkatenation der Zeichen des Alphabetes bzw. der Wörter der Sprache entsteht. Da auch die leere Menge mit einbezogen wird, ist diese in jeder kleeneschen Hülle enthalten.

Um die kleenesche Hülle darzustellen, wird an das Alphabet beziehungsweise an die Sprache einfach ein Stern-Operator angehängt: * und L*.

Da die Konkatenation beliebig erfolgen kann, ist die kleenesche Hülle unendlich groß. Wenn man beispielsweise eine Sprache L hat, die aus den Wörtern „00“ und „101“ besteht, die also entsprechen L = {00, 101} ist. Dabei muss die kleenesche Hülle die leere Menge enthalten: L* = {}. Die Konkatenation eines Wortes mit der leeren Menge liefert allein das Wort als Ergebnis: L*={}. Jetzt folgen unendlich viele Möglichkeiten die Worte zu kombinieren: L* = {}. Eine Ausnahme ist die Potenzierung einer leeren Menge. Diese bleibt unverändert: {}* = {}* = {}