Was ist formelle Sprache?

Eine formelle (meist sagt man: formale) Sprache ist in der Informatik eine Menge von Wörtern, die nach festen Regeln aus einem Alphabet gebildet werden. Ein Alphabet ist die Menge erlaubter Zeichen, und ein Wort ist eine endliche Folge solcher Zeichen.

Was heißt formal richtig?

Formal richtig heißt, dass etwas syntaktisch korrekt ist, also den Aufbau-Regeln der Sprache entspricht. Die Bedeutung spielt dabei keine Rolle, weshalb ein Satz formal richtig sein kann, aber semantisch unsinnig wirkt. Ein Beispiel ist „Eine Blume kocht flüssige Uhren“.

Was bedeutet „konkatenativ“?

„Konkatenativ“ bedeutet „durch Konkatenation“, also durch Verkettung von Zeichen oder Wörtern. Bei Sprachen meint das: Man hängt ein Wort aus der einen Sprache an ein Wort aus der anderen an und sammelt alle so entstehenden Wörter. Zum Beispiel wird aus „aa“ und „ae“ das Wort „aaae“.

Was ist der Unterschied zwischen dem leeren Wort und der leeren Menge?

Das leere Wort ist ein Wort mit Länge 0 und gehört als einzelnes Element zu einer Sprache, zum Beispiel . Die leere Menge ist eine Sprache ohne jedes Wort, sie enthält also gar kein Element. Deshalb bleibt beim Verketten mit ein Wort gleich, mit entsteht keine Ausgabe.

Video

Formale Sprachen

Wichtige Inhalte in diesem Video

Formale Sprache

(00:14)

Operationen auf formale Sprachen

(01:18)

Konkatenation

(02:14)

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.

Studyflix vernetzt: Hier ein Video aus einem anderen Bereich

Nach Beantwortung speichern wir deine Antwort, um Studyflix zu verbessern. Mehr dazu erfährst du in unserer Datenschutzerklärung.

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

Formale Sprachen — häufigste Fragen

(ausklappen)

Was ist formelle Sprache?

Eine formelle (meist sagt man: formale) Sprache ist in der Informatik eine Menge von Wörtern, die nach festen Regeln aus einem Alphabet gebildet werden. Ein Alphabet ist die Menge erlaubter Zeichen, und ein Wort ist eine endliche Folge solcher Zeichen.
Was heißt formal richtig?

Formal richtig heißt, dass etwas syntaktisch korrekt ist, also den Aufbau-Regeln der Sprache entspricht. Die Bedeutung spielt dabei keine Rolle, weshalb ein Satz formal richtig sein kann, aber semantisch unsinnig wirkt. Ein Beispiel ist „Eine Blume kocht flüssige Uhren“.
Was bedeutet „konkatenativ“?

„Konkatenativ“ bedeutet „durch Konkatenation“, also durch Verkettung von Zeichen oder Wörtern. Bei Sprachen meint das: Man hängt ein Wort aus der einen Sprache an ein Wort aus der anderen an und sammelt alle so entstehenden Wörter. Zum Beispiel wird aus „aa“ und „ae“ das Wort „aaae“.
Was ist der Unterschied zwischen dem leeren Wort und der leeren Menge?

Das leere Wort $\varepsilon$ ist ein Wort mit Länge 0 und gehört als einzelnes Element zu einer Sprache, zum Beispiel $\{\varepsilon\}$ . Die leere Menge $\emptyset$ ist eine Sprache ohne jedes Wort, sie enthält also gar kein Element. Deshalb bleibt beim Verketten mit $\varepsilon$ ein Wort gleich, mit $\emptyset$ entsteht keine Ausgabe.

Automaten und Sprachen verstehen

Formale Sprachen gehören zum Themenfeld Automaten und Sprachen und bilden eine wichtige Grundlage der Informatik. Wer sich mit Automaten und Sprachen beschäftigt, ordnet Zeichen, Wörter und Regeln klar voneinander ab. Dabei wird verständlich, wie Computer Eingaben prüfen und nach festen Mustern verarbeiten. Im Informatikbereich findest du passende Videos zu diesem und verwandten Themen.

zur Videoseite: Formale Sprachen