Eine formale Sprache ist eine abstrakte Sprache, bei der im Unterschied zu natürlichen Sprachen oft nicht die Kommunikation im Vordergrund steht, sondern die mathematische Verwendung. Eine formale Sprache besteht aus einer bestimmten Menge von Symbolketten (im Allgemeinen Zeichenketten) („Worte“ der Sprache), die aus einem Zeichen-/Symbolvorrat („Alphabet“, Grundsymbole) zusammengesetzt werden können. Anwendung finden formale Sprachen in der Linguistik, der Logik und der theoretischen Informatik. Show Formale Sprachen eignen sich zur (mathematisch) präzisen Beschreibung des Umgangs mit Zeichenketten. So können zum Beispiel Datenformate oder ganze Programmiersprachen spezifiziert werden. Zusammen mit einer formalen Semantik erhalten die definierten Zeichenketten eine (mathematische) Bedeutung. Bei einer Programmiersprache kann damit einer Programmieranweisung (als Teil der formalen Sprache) ein eindeutiges Maschinenverhalten (als Teil der Semantik) zugeordnet werden. Aufbauend auf formalen Sprachen können aber auch Logikkalküle definiert werden, mit denen man mathematische Schlüsse ziehen kann. In Verbindung mit formal definierten Programmiersprachen können Kalküle helfen, Programme auf ihre Korrektheit zu überprüfen. DefinitionEine formale Sprache Ein Alphabet legt die Zeichen fest, aus denen ein „Wort“ der Sprache gebildet werden kann. Zum Beispiel kann man die Dezimaldarstellung jeder natürlichen Zahl aus dem Alphabet bilden. Alle aus einem gegebenen Alphabet beliebig bildbaren Wörter mit endlicher Länge (Länge 0 oder länger), deren jeder einzelne Buchstabe Element von ist, diese größtmögliche Wortmenge zum Alphabet , nennt man die Kleenesche Hülle des Alphabetes , kurz . Eine formale Sprache über einem Alphabet ist also eine bestimmte Teilmenge der Kleeneschen Hülle ihres Alphabets – im Allgemeinen ist also nicht jede beliebige Zeichenkombination ein gültiges Wort der Sprache. Formale Sprachen können leer, endlich oder unendlich sein; maximal können sie die gesamte Kleenesche Hülle ihres Alphabetes umfassen. Sie können über eine mathematische Bedingung an ihre Wörter definiert sein: „Die Sprache … ist die Menge aller Wörter, für die gilt …“. Die in der theoretischen Informatik auftretenden Sprachen sind jedoch meistens spezieller durch ein bestimmtes Ersetzungsverfahren definiert – Regeln, wie die Alphabet-Zeichen kombiniert sein/werden dürfen. Von den Ersetzungsverfahren gibt es verschiedene Typen: Semi-Thue-Systeme, Chomsky-Grammatiken, Lindenmayer-Systeme u.a. Bei solchen Ersetzungsverfahren geht man beispielsweise von einer spezifischen Start-Zeichenkette aus, die man durch wiederholte („rekursive“) Anwendung der Regeln (Text-Ersetzungen) schrittweise in Wortgebilde überführt, die dann als ganzes, oder nur ein vorgegebener Abschnitt davon, als Wörter der Sprache gelten. Man redet hier auch von generativen Grammatiken, weil die Wörter einer Sprache über solche Textsubstitutionen schrittweise erzeugt werden. Umgekehrt kann man Sprachen auch definieren als die Menge aller Wörter, aus denen (über das Ersetzungsverfahren der Sprache) ein bestimmtes vorgegebenes Wort oder eines von mehreren vorgegebenen Wörtern erzeugbar ist. („Es gehört alles zur Sprache, was sich über die Regeln auf … zurückführen lässt.“) Abgrenzung von natürlichen SprachenMit Hilfe formaler Sprachen können auch natürliche Sprachen modelliert werden, vor allem deren Syntax. Beim Vergleich formaler Sprachen mit natürlichen Sprachen ist aber zu beachten, dass natürliche Sprachen oberhalb der elementaren Laut-Zeichen mindestens die zwei übereinander liegenden Hierarchieebenen des Wortes und des Satzes besitzen. Die Regeln für deren Aufbau trennt man gewöhnlich in Morphologie zum einen und in Syntax zum anderen. In formalen Sprachen dagegen liegt über dem elementaren Alphabet-Zeichen oft nur die eine Hierarchieebene des formalen Wortes, man redet im Hinblick auf den Bau der Wörter formalsprachlich von Syntax. Wenn eine natürliche Sprache mittels einer formalen modelliert wird, dann werden also die Sätze der natürlichen Sprache in formalsprachlicher Betrachtung Wörter genannt. Außerdem haben Äußerungen in natürlicher Sprache eine natürliche Bedeutung, während die Bedeutung formaler Sprachen stets auf ebenfalls formalem Weg definiert werden muss. Beispiele
Operationen auf formalen SprachenZwei Sprachen über dem Alphabet und über dem Alphabet sind banalerweise beide Sprachen auch über , also Mengen von Wörtern aus . Deshalb sind auch Sprachen über . Weitere Operationen auf Sprachen sind: KonkatenationDie Konkatenation zweier Sprachen und ist die Sprache der Wörter, die durch Hintereinanderschreibung (Konkatenation) je eines beliebigen Wortes aus und aus entsteht: .So sind zum Beispiel die Konkatenationen von verschiedenen Sprachen über dem Alphabet : Das neutrale Element der Konkatenation ist die Sprache, welche nur das leere Wort enthält. So gilt für jede beliebige Sprache : Das absorbierende Element der Konkatenation ist die leere Sprache, sodass für jede Sprache gilt: Die Konkatenation von Sprachen ist wie die Konkatenation von Wörtern assoziativ, aber nicht kommutativ. So ist zum Beispiel: aber: Da außerdem die Potenzmenge der Kleeneschen Hülle eines beliebigen Alphabets (die gleich der Menge aller Sprachen ist, die aus gebildet werden können) abgeschlossen bezüglich Konkatenation ist, bildet sie zusammen mit der Konkatenation als Operator und der Sprache des leeren Wortes als neutrales Element ein Monoid. PotenzDie Potenz einer Sprache ist die -fache Konkatenation dieser Sprache mit sich selbst. Sie ist rekursiv definiert mit: (für )So sind zum Beispiel: Im Speziellen gilt für jede einelementige, formale Sprache (mit ) und jedes : Kleene-*-Abschluss und Kleene-+-AbschlussDer Kleene-*-Abschluss (Kleenesche Hülle, auch Iteration genannt) und der Kleene-+-Abschluss (positive Hülle) einer formalen Sprache sind definiert über die Vereinigung der Potenzsprachen von : Wichtige formale Sprachklassen
HistorischesAls eine der ersten formalen Sprachen wird Gottlob Freges Begriffsschrift erachtet, eine wie Frege schrieb „Formelsprache des reinen Denkens“. Axel Thues im Jahre 1914 eingeführtes Semi-Thue-System, das verwendet werden kann, um Zeichenketten zu transformieren, hatte ebenfalls Einfluss auf die Entwicklung formaler Grammatiken. ZitatDie heutige Grundlagenforschung ist beherrscht
– Heinrich Scholz im Jahre 1941: Eine neue Gestalt der Grundlagenforschung Heinrich Scholz traf sich 1944 mit Konrad Zuse, der im Zuge seiner Doktorarbeit an seinem Plankalkül arbeitete. Im März 1945 sprach ihm Scholz für die Anwendung seines Logikkalküls seine Anerkennung aus. Siehe auchAnwendungen siehe in:
Literatur
Basierend auf einem Artikel in: © biancahoegel.de Datum der letzten Änderung: Jena, den: 14.08. 2022 Wann ist eine Sprache formal?Unter formalen Sprachen verstehen wir in der Informatik und Mathematik Sprachen, deren Wörter und Sätze aus einer begrenzten Menge von Symbolen bestehen, welche nicht beliebig, sondern nur strengen Regeln entsprechend zusammengesetzt sein dürfen.
Wann ist eine Grammatik regulär?Definition: Reguläre Grammatik
Eine Grammatik G = ( N , T , P , S ) G = (N,T,P,S) G=(N,T,P,S) heißt regulär, wenn in allen Produktionen jeweils genau ein Nichtterminal ersetzt werden kann durch genau ein Nichtterminal oder genau ein Terminal oder genau ein Nichtterminal verknüpft mit genau einem Terminal.
Welche formalen Sprachen gibt es?Beispiele. Die Programmiersprache C ist eine formale Sprache. ... . Die natürlichen Zahlen in unärer Darstellung:. Die unäre Sprache über , die nur Wörter quadratischer Länge enthält:. Die Sprache aller Palindrome: , ... . Die Dezimalkodierung der Primzahlen: . ... . Die Morse- oder Thue-Folge: ,. Wann ist eine Sprache erkennbar?Man nennt die Sprache L ohne jeden weiteren Zusatz erkennbar, wenn sie durch ein endliches Monoid erkennbar ist.
|