Theoretische Informatik

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.

Inhaltsübersicht

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.

Formale Sprachen, Formale Sprache
direkt ins Video springen
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

Auf formale Sprachen können auch Mengenoperationen angewandt werden. Gegeben seien dabei beispielsweise die zwei Sprachen L1 und L2 . 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.
Formale Sprachen Mengenoperationen
direkt ins Video springen
Mengenoperationen

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 L1 und L2 ergibt eine neue formale Sprache, die alle möglichen Aneinanderreihungen der Wörter u und v aus den Sprachen L1 und L2 enthält. Dabei stellt, u ein Element der Sprache L1, und v ein Element der Sprache L2 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 L1 besteht aus den Wörtern „aa“ und „ee“, die Sprache L2 hingegen aus den Wörtern „ae“ und „ea“.

L_{1} = {aa, ee}

L_{2} = {ae, ea}

Die Sprachen L1 und L2 sollen konkateniert werden. Die neue Sprache enthält alle Wörter, die mit einem Wort aus L1 beginnen und auf ein Wort aus L2 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}


Andere Nutzer halten diese Inhalte aus dem Bereich „Theoretische Informatik“ für besonders klausurrelevant

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte lade anschließend die Seite neu.