Formale Sprache
Eine formale Sprache ist eine Menge von Wörtern endlicher Länge über einem endlichen Alphabet. Diese etwas mathematische Ausdrucksweise soll im folgenden näher erläutert werden.
Ein Alphabet ist einfach eine Menge von Symbolen und endlich bedeutet hier, dass dieses Alphabet nur endlich viele (und nicht unendliche viele) Symbole enthält. Man kann sich ein Alphabet also wie ein normales Alphabet vorstellen, beispielsweise das der deutschen Sprache.
Ein Wort über einem Alphabet ist dann einfach eine Folge von Symbolen aus diesem Alphabet und endlich bedeutet hier, dass diese Folge abbricht, es also nur endlich viele (und nicht unendliche viele) Glieder in dieser Folge gibt. Anschaulich kann man sich ein Wort also wie ein normales geschriebenes Wort vorstellen. Es gibt dabei einen Spezialfall, das sogenannte leere Wort, bei dem die Folge der Symbole die Länge 0 besitzt. Dieses wird meist durch symbolisiert.
Man kann solche Wörter verketten, d.h. in beliebiger Reihenfolge hintereinander schreiben und so neue Wörter bilden. Das leere Wort ist dabei das neutrale Element bezüglich der Verkettung, d.h. die Verkettung eines Wortes mit dem leeren Wort ist das Wort selbst.
Eine formale Sprache ist nun eine Menge von Wörter, wobei die Menge dieser Wörter endlich oder unendlich sein kann. Man spricht dann auch von einer endlichen oder unendlichen Sprache.
Noam Chomsky hat eine Hierarchie von Grammatiken aufgestellt, die verschiedene Typen von formalen Sprachen erzeugen. Diese ist heute unter dem Namen Chomsky-Hierarchie bekannt.
Beispiele
Wir betrachten das Alphabet . Dann sind und zum Beispiel Wörter über diesem Alphabet. ist kein Wort über diesem Alphabet, da , und nicht im Alphabet vorkommen.
Die Verkettung der Wörter und (in dieser Reihenfolge) ergibt dann das Wort . Die Verkettung von mit ergibt .
Eine formale Sprache über dem Alphabet könnte zum Beispiel die Menge aller Wörter sein, die erst mit einer Folge von 's beginnt, dann mit einer Folge von 's weitergeht und zuletzt mit einer Folge von 's endet.
