Video anzeigen

Formale Sprachen

Wichtige Inhalte in diesem Video

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.

Inhaltsübersicht

Formale Sprache

im Videozur Stelle im Video springen

(00:14)

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.

Formale Sprachen, Formale Sprache — Formale Sprachen

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

im Videozur Stelle im Video springen

(01:18)

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: $L_{1} \cup L_{2} mit \omega \in L_{1} \lor\omega \in L_{2}$
Durchschnittsmenge: $L_{1} \cap L_{2} mit \omega \in L_{1} \land\omega \in L_{2}$
Differenzmenge: $L_{1}∖L_{2} mit \omega \in L_{1} \land\omega \notin L_{2}$

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.

Konkatenation

im Videozur Stelle im Video springen

(02:14)

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.

$L_{1} \circ L_{2} = {uv | u \in L_{1}, v \in L_{2} }$

Konkatenation Beispiel

Als Beispiel soll dabei ein Alphabet zweier Sprachen aus den Buchstaben „a“ und „e“ bestehen: $\Sigma= {a, e}$

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

$L_{1} = {aa, ee}$

$L_{2} = {ae, 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.

$L_{1} \circ L_{2} = {aaae, aaea, eeae, eeea}$

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

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: $\omega^4 = \omega\omega\omega\omega$

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: ${a,e}^2={a, e}\circ{a, e}={aa, ae, ea, ee}$

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

$\omega^0 = \varepsilon$

$L^0 = \varepsilon$

Außerdem ergibt die leere Menge potenziert ebenfalls die leere Menge: $\varepsilon^0 = \varepsilon$

Kleenesche Hülle

Die kleenesche Hülle eines Alphabets $\Sigma$ 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: $\Sigma$ * 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* = { $\varepsilon$ }. Die Konkatenation eines Wortes mit der leeren Menge liefert allein das Wort als Ergebnis: L*={ $\varepsilon, 00, 101$ }. Jetzt folgen unendlich viele Möglichkeiten die Worte zu kombinieren: L* = { $\varepsilon, 00, 101, 0000, 0101, 10100,...$ }. Eine Ausnahme ist die Potenzierung einer leeren Menge. Diese bleibt unverändert: {}* = { $\varepsilon$ }* = { $\varepsilon$ }