Formale Sprache

Formale Sprachen sind mathematische Objekte, die besonders in der theoretischen Informatik, insbesondere bei Berechenbarkeits- und Komplexitätstheorie, sowie beim Compilerbau, Anwendung finden.

Definition

Eine formale Sprache $L$ ist eine Menge von Wörtern über einem Alphabet $\Sigma$. Dabei ist ein Alphabet einfach eine endliche Menge von Objekten, die man wiederum Symbole oder Zeichen nennt. Ein Wort ist eine Folge bzw. Liste von Symbolen (Programmierer sagen String oder Zeichenkette dazu). Die Länge eines Wortes ist die Anzahl der Folgenglieder, z.B. $w=hallo\implies |w|=5$.

Zwei Wörter $u$ und $v$ kann man zu einem neuen Wort $w$ aneinanderreihen, man bezeichnet diese Operation als Konkatenation und schreibt $w=u\cdot v$ oder kürzer $w=uv$. Es gibt auch ein leeres Wort $\varepsilon$, welches das neutrale Element bezüglich der Konkatenation darstellt, denn für jedes Wort $u$ gilt $u\varepsilon =\varepsilon u=u$.

Man sieht, man betreibt in der theoretischen Informatik Algebra mit Wörtern und Zeichen, statt wie gewohnt mit Zahlen.

Die Konkatenation zweier Sprachen $L_{a}$ und $L_{b}$ ist $L_{a}\cdot L_{b}=\{uv|u\in L_{a},v\in L_{b}\}$. Also alle Worte, die man bilden kann, indem ein Wort aus $L_{a}$ und ein Wort aus $L_{b}$ aneinandergereiht werden.

Man kann durch $L^{n+1}=L^{n}\cdot L$ induktiv die Potenz $L^{n}$ von Sprachen für $n\in \mathbb {N}$ mit $\mathbb {N} =\{0,1,2,\ldots \}$ definieren, dabei wird $L^{1}=L$ und $L^{0}=\{\varepsilon \}$ definiert (beachte: die Menge, die nur das leere Wort enthält, ist selbst nicht leer!)

Jetzt können wir die Menge aller endlichen Worte über dem Alphabet $\Sigma$ hinschreiben: $L=\Sigma ^{*}$, wobei $M^{*}=\bigcup _{i\in \mathbb {N} }M^{i}$ und wir hier die Symbole $a$ aus $\Sigma$ mit den Wörtern $a$ der Länge 1 identifizieren.

Die $.^{*}$ Operation wird auch als endlicher Abschluss bezeichnet, der Operator als Kleene Stern.

Die Menge dieser Wörter kann endlich oder unendlich sein. Man spricht dann auch von einer endlichen oder unendlichen Sprache.

Noam Chomsky hat eine Hierarchie von formalen Grammatiken aufgestellt, die verschiedene Typen von formalen Sprachen erzeugen. Diese ist heute unter dem Namen Chomsky-Hierarchie bekannt.

Während Grammatiken Wörter einer Sprache produzieren, werden Automaten verwendet, um Sprachen zu akzeptieren, das heisst zu entscheiden, ob ein Wort zu einer Grammatik passt. Siehe dazu auch Parser.

Beispiele

Wir betrachten das Alphabet $\Sigma =\{a,b,c\}$. Dann sind $u=abcab$ und $v=aaabbb$ zum Beispiel Wörter über diesem Alphabet. $w=abcdef$ ist kein Wort über diesem Alphabet, da $d$, $e$ und $f$ nicht im Alphabet $\Sigma$ vorkommen.

Die Verkettung der Wörter $aaa$ und $bbbcc$ (in dieser Reihenfolge) ergibt dann das Wort $aaabbbcc$. Die Verkettung von $aaabb$ mit dem "leeren Wort" $\varepsilon$ ergibt erneut $aaabb$.

Eine formale Sprache über dem Alphabet $\{a,b,c\}$ könnte zum Beispiel die Menge aller Wörter sein, die erst mit einer Folge von $a$'s beginnt, dann mit einer Folge von $b$'s weitergeht und zuletzt mit einer Folge von $c$'s endet. Diese Sprache könnte formal als $L=\{a^{i}b^{j}c^{k}|i,j,k\in \mathbb {N} \}$ beschrieben werden.

Menschliche Sprachen

Menschliche Sprachen basieren auf endlichen Alphabeten, deshalb sind sie als Teilmenge in der Menge aller Wörter über dem betreffenden Alphabet enthalten und somit auch formale Sprachen. Wissenschaftliche Fachrichtungen wie die Computerlinguistik beschäftigen sich mit der algorithmischen Bearbeitung von menschlichen Sprachen, zum Beispiel um maschinelle Übersetzung zu ermöglichen. Inwiefern dies effizient möglich ist, hängt von der bisher ungeklärten Einstufung der natürlichen Sprachen in die Chomsky-Hierarchie ab.