Was sind formale Sprachen ?

Formale Sprachen sind abstrakte Sprachen mit dem Ziel, den Umgang mit Zeichenketten zu beschreiben. Im Gegensatz zu unseren natürlichen Sprachen dienen formale Sprachen also eher dazu, mathematische Beschreibungen für den Umgang eines Computers mit Zeichenketten zu finden und so Codierungen, Datenformate oder Programmiersprachen näher zu spezifizieren. 

Aber fangen wir zunächst mit Sprachen im Allgemeinen an, sprich mit den uns bekannten natürlichen Sprachen Teilen und Beschreiben komplexer Inhalte. 

Jede menschliche Sprache, zumindest die mir bekannten Sprachen wie Deutsch, Englisch etc. folgen gewissen Regeln. Diese Regeln lassen sich unterteilen in Syntax, Grammatik und Semantik. 

Die Semantik, sprich die Bedeutung eines Wortes, unterschiedet menschliche (natürliche) Sprachen von künstlichen, formalen Sprachen. Deutlich wird dies, wenn man die Artikulation und Betonung von Wörtern miteinbezieht. So können Wörter in menschlichen Sprachen je nach Kontext bei gleicher  Grammatik und Syntax eine diametrale Semantik (Bedeutung) aufweisen. Am besten wird dies bei der Verwendung von Sarkasmus deutlich.

Formale Sprachen unterscheiden sich zu menschlichen Sprachen also insofern, als dass sie mathematisch fassbar sind und die Semantik keine Rolle spielt.

Formale Sprachen sind also insofern künstliche Sprachen, welche es Computern ermöglichen, Daten und Informationen zu verarbeiten.

 Aufbau/Bestandteile von formalen Sprachen:

Auch wen  formale Sprachen sich im Punkt Semantik von der menschlichen Sprache klar abgrenzen, so gibt es dennoch viele Gemeinsamkeiten.

So liegen formalen Sprachen ebenfalls ein Alphabet, also eine nichtleere Menge aus Zeichen/Symbolen zugrunde, welche durch eine Verkettung Wörter bilden können.

In diesem Beispiel haben wir ein Alphabet definiert, welches die 6 Zeichen {a,b,c,d,7,+} enthält. Ein definiertes Alphabet bezeichnet man mit mit Groß Sigma.

Die Elemente eines Alphabetes bezeichnet man jeweils als klein Sigma. 

Schauen wir uns daraufhin mal ein Beispiel anhand der natürlichen Zahlen an. Natürliche Zahlen umfassen alle Ganzzahlen, welche positive Vorzeichen haben. 

Wen  wir nun ein Alphabet bestehend aus natürlichen Zahlen konzipieren wollen, dann legen wir in den geschweiften Klammern eine Teilmenge der unendlichen Menge der natürlichen Zahlen fest, indem wir ein endliche Menge der natürlichen Zahlen auswählen.

Da ein Alphabet eine nichtleere Menge ist, muss mindestens eine natürliche Zahl ausgewählt werden.

Die Elemente eines Alphabets, in diesem Fall die natürlichen Zahlen, müssen endlich sein, sodass das letzte Element definiert werden muss. In diesem Fall haben wir eine allgemeine Formulierung verwendet, indem das Alphabet alle natürlichen Zahlen bis zu einer definierten Natürlichen Zahl n enthält. In diesem Fall ergibt sich der günstige Fall, dass das letzte Element nicht nur die letzte Zahl ist und somit das Alphabet beendet, sondern gleichzeitig auch noch äquivalent ist zur Gesamtmenge der Elemente.

Dies hängt damit zusammen, dass die natürlichen Zahlen in den geschweiften Klammen beginnend bei 1 inkrementiert (sukzessive um 1 erhöht) werden {1,2,3....}, bis das letzte Element des Alphabets erreicht ist.

Wenn n=10, so hätten wir ein Alphabet mit der Elementemenge {1,2,3,4,5,6,7,8,9,10}={1,2,3,...,10}.

 Wörter/Zeichenketten 

Genau wie bei den menschlichen Sprachen können auch bei den formalen Sprachen Wörter aus den Elementen des Alphabets gebildet werden, indem man einzelne Element des Alphabets miteinander verknüpft.

Ein solches Wort wird in der theoretischen Informatik mit dem griechischen W  bezeichnet. Die einzelnen Elemente/Zeichen eines Alphabets werden als Wi bezeichnet.

Für das leere Wort, sprich ein Wort W mit einer leeren Menge an Elementen, schreibt man Epsilon.

Wichtig !!!!

Ein leeres Wort ist kein Element des Alphabets !!!

In folgendem Bild kann man die Definition eines Wortes aus der Elementemenge des Alphabets sehen. Der Pfeil bedeutet, dass ein Wort abgebildet wird aus einer definierten endlichen Menge n aus der Menge der natürlichen Zahlen. Anders gesagt: Ein Wort ist eine Abbildung aus einer Menge A (Alphabet).

Die Abbildung wird in diesem Fall rechts von dem Summenzeichen näher definiert, indem allgemein dargelegt wird, dass ein Wort aus einer definierten Menge aller natürlichen Zahlen als zusammengesetzte Elemente die gleichen Elemente dieser definierten Menge natürlicher Zahlen enthalten kann.

Ein Wort ist zwar endlich, allerdings können Wörter eine größere Elementemenge  haben als das Alphabet, sofern einzelne Zeichen mehrmals auftreten. Ein Wort kann jedoch maximal genauso viele unterschiedliche Zeichen wie ein Alphabet haben.

Die Art und Weise, inwiefern aus den Element eines Alphabets Wörter gebildet werden können, kann in  der Grammatik einer formalen Sprache festgelegt werden.

Da ein Wort aus den Elementen eines Alphabets durch Verkettung entsteht und diese Verkettung gewissen Regeln folgt, bezeichnet man eine Teilmenge der Gesamtmenge aller möglichen Wörter über einem Alphabet als formale Sprache.

Die Art und Weise, wie die Teilmenge gestaltet ist, wird bestimmt durch die Grammatik einer formalen Sprache.

Zuletzt aktualisiert 06.09.2020