Was ist formale Sprache?
Eine formale Sprache ist eine abstrakte Sprache, welche zum Ausdruck von Definitionen, Anweisungen und Logik genutzt wird. Sie besteht aus einer bestimmten Menge von Zeichen- oder Symbolketten (Wörter), die wiederum aus bestimmten Zeichen (Alphabet, Symbole) gebildet werden. Formale Sprachen werden in den Bereichen Informatik, Mathematik und Linguistik genutzt.
Die Definition lautet:
Eine formale Sprache L über einem Alphabet Σ ist eine Teilmenge der Kleeneschen Hülle des Alphabets: L⊆Σ*.
Die Kleeneschen Hülle Σ* definiert dabei die Menge aller Wörter, die aus dem im Alphabet A enthaltenen Zeichen durch beliebige Konkatenation (Verkettung von Zeichenketten) zusammengesetzt werden können. Dabei ist das leere Wort (eine Zeichenkette der Länge 0) enthalten.
Allgemein wird auch bei formalen Sprachen der Syntax und die Semantik unterschieden. Der Syntax beschreibt die Grammatik der Sprache, also die Regeln, mit denen die Sprache zusammengesetzt wird. Die Semantik beschreibt hingegen die Bedeutung der Wörter. Der Satz: „Die Lampe schließt das Fenster mit einer Kuh.“ ist syntaktisch korrekt, aber semantisch unsinnig. Daher brauchen Sprachen die richtige Zusammenarbeit von Syntax und Semantik.
Formale Sprache in der Informatik
In der theoretischen Informatik werden formale Sprachen zur Modellbildung, Informationsverarbeitung und für den Compilerbau genutzt. Sie werden durch bestimmte Ersetzungsverfahren definiert. Dies sind Regeln, wie die Zeichen des Alphabets kombiniert werden dürfen. Gängige Ersetzungsverfahren sind beispielsweise Chomsky-Grammatiken, Semi-Thue-Systeme oder die Lindenmayer-Systeme.
In der angewandten Informatik finden formale Sprache in Form von Programmiersprachen Anwendung. Der Quellcode (die gesamten Anweisungen in Form einer Programmiersprache) kann in einem einfachen Texteditor erstellt werden. Dieser muss in eine passende Maschinensprache (einem Binärcode) übersetzt werden. Je nach Zeitpunkt der Übersetzung gibt es hierfür verschiedene Möglichkeiten. Mithilfe eines Compilers wird der Quellcode vor der Ausführung des Programms übersetzt. Ein JIT-Compiler (Just-in-Time-Compiler) oder ein Interpreter übersetzt den Quelltext, während das Programm läuft. Eine Kombination von beiden ist auch möglich und wird beispielsweise bei der Programmiersprache Java genutzt.
Programmiersprachen lassen sich in verschiedene Klassen unterteilen, den sogenannten Programmierparadigmen. Die drei bekanntesten Anwendungen formaler Sprache sind die objektorientierte, die funktionale und die imperative Programmierung.
Eine objektorientierte Programmierung basiert auf Daten und Objekten. Das Objekt gehört zu einer übergeordneten Klasse, besitzt bestimmte Attribute und es werden ihm verschiedene Methoden zugeordnet.
Bei einer funktionalen Programmierung sind alle Bestandteile des Computerprogramms ausschließlich Funktionen, sogar das Programm selbst. Die Funktionen können zu Funktionen höherer Ordnung verknüpft werden, wie in der Mathematik.
Von einer imperativen Programmierung spricht man, wenn das Computerprogramm aus Anweisungen besteht, welche dem Rechner vorgeben, was er wann genau zu tun hat. Dafür werden Schleifen oder Verzweigungen als Kontrollstrukturen genutzt.
Was sind Beispiele für formale Sprache?
1. Programmiersprachen wie:
- C++, Java, JavaScript und Python als objektorientierte Programmierung
- Haskell, LISP und Scheme als funktionale Programmierung
- ALGOL, Cobol, C und FORTRAN als imperative Programmierung
2. Sprache der Palindrome: ein Palindrom ist ein Wort, welches vorwärts und rückwärts geschrieben identisch ist. Der formale Ausdruck lautet:
- Ein Palindrom ist ein Wort u über dem Alphabet Σ mit der Eigenschaft u=uR.
- Dabei sorgt der Operator R für Umkehrung der Zeichenfolge.
3. Morse-Folge (auch Morse-Thue-Sequenz, Thue-Morse-Sequenz genannt): ist eine unendliche Binärfolge, die nach konkreten Regeln gebildet wird. Als formale Sprache beginnt sie mit 0, 01, 0110, 01101001, 0110100110010110…
