Formale Sprache
Formale Sprachen sind mathematische Modelle von Sprachen, die besonders in der theoretischen Informatik, insbesondere bei Berechenbarkeitstheorie und dem Compilerbau Anwendung finden.
Mathematisch korrekt formuliert ist eine formale Sprache 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 so genannte leere Wort, bei dem die Folge der Symbole die Länge 0 besitzt. Dieses wird meist durch
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örtern, 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.
Wir betrachten das Alphabet
Die Verkettung der Wörter
Eine formale Sprache über dem Alphabet
zh-cn:形式语言
zh-tw:形式語言Definition
symbolisiert.Beispiele
. Dann sind 
und 
zum Beispiel Wörter über diesem Alphabet. 
ist kein Wort über diesem Alphabet, da 
, 
und 
nicht im Alphabet vorkommen.
und 
(in dieser Reihenfolge) ergibt dann das Wort 
. Die Verkettung von 
mit ergibt . 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.\n
