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 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.
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.
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.
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.
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.
Als Beispiel soll dabei ein Alphabet zweier Sprachen aus den Buchstaben „a“ und „e“ bestehen:
Die Sprache L1 besteht aus den Wörtern „aa“ und „ee“, die Sprache L2 hingegen aus den Wörtern „ae“ und „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.
Wichtig zu wissen ist außerdem, dass eine Konkatenation eines Wortes mit der leeren Menge das Wort unverändert zurückgibt, also:
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:
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: {}* = {
}* = {
}
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.