Formale Sprachen

Einführung

Die Theorie der formalen Sprachen nehmen in der theoretischen Informatik breiten Raum ein. Hier wird das theoretische Fundament zum Verständnis von Anwendungen zum Beispiel aus dem Bereich der künstlichen Intelligenz oder dem Compiler gelegt. Der Begriff "formale Sprache" unterstreicht die Abgrenzung zur natürlichen und zur Programmiersprache. In formalen Sprachen spielt die Semantik, d.h. die Bedeutung der Sätze einer Sprache, keine Rolle! Quelle (Informatik, Dr. Lutz Engelmann, Paetec, 2002 S. 404 ff)

for(int i=1;i<=5;i++){

    System.out.println("Hallo");

}

In der Programmiersprache Java bedeutet das Code-Beispiel, dass das Wort "Hallo" am Bildschirm fünfmal untereinander geschrieben wird. Das Wort for beutet, dass eine Schleife eingeleitet wird. Die Laufbedingung wird im folgenden Klammerpaar angegeben.

Eine formale Sprache ist eine abstrakte Sprache, bei der im Unterschied zu konkreten Sprachen oft nicht die Kommunikation im Vordergrund steht, sondern die mathematische Verwendung. Eine formale Sprache besteht aus einer bestimmten Menge von Zeichen. Sie werden auch Wort genannt. Der Zeichenvorrat aus dem Worte gebildet werden können nennt sich Alphabet.

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. So kann ein Programme auf seine Korrektheit überprüfen werden (siehe Syntax und Compiler).

Definition

Eine formale Sprache L über einem Alphabet Σ  ist eine Teilmenge der Kleeneschen Hülle des Alphabets: L ⊆ Σ∗. Die kleenesche Hülle (auch endlicher Abschluss, Kleene-*-Abschluss, Verkettungshülle oder Sternhülle genannt) eines  Alphabets Σ  oder einer formalen Sprache L ist die Menge aller Wörter, die durch beliebige Konkatenation (Verknüpfung) von Symbolen des Alphabets Σ  bzw. von Wörtern der Sprache L gebildet werden können, wobei das leere Wort ε  inbegriffen ist.

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 Σ= { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 }  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 Σ, diese größtmögliche Wortmenge zum Alphabet Σ, nennt man die Kleenesche Hülle des Alphabetes Σ, kurz Σ∗.

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. Bei 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.“)