Formale Sprache

Definition

Mathematisch korrekt formuliert ist eine formale <math>L</math> eine Menge von Wörtern endlicher Länge über einem Alphabet <math>\Sigma</math>:

<math>L\subseteq\Sigma^*</math> (hierbei <math>M^*:=\bigcup_{i\in\mathbb{N}} M^i</math>).

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

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

Beispiele

Wir betrachten das Alphabet <math>\{a b Dann sind <math>abcab</math> und <math>aaabbb</math> zum Beispiel über diesem Alphabet. <math>abcdef</math> ist kein Wort diesem Alphabet da <math>d</math> <math>e</math> und <math>f</math> im Alphabet vorkommen.

Die Verkettung der Wörter <math>aaa</math> und (in dieser Reihenfolge) ergibt dann das Wort Die Verkettung von <math>aaabb</math> mit dem "leeren <math>\epsilon</math> ergibt erneut <math>aaabb</math>.

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

Menschliche Sprachen

Natürliche Sprachen sind keine formalen Sprachen. befassen sich wissenschaftliche Fachrichtungen wie die Computerlinguistik damit natürliche Sprachen als formale Sprachen (beispielsweise um maschinelle Übersetzung zu ermöglichen). Wenn dies gelingt dann daraus dass die menschlichen Sprachen eine Teilmenge der formalen Sprachen sind.

Bücher zum Thema Formale Sprache

Dieser Artikel von Wikipedia unterliegt der GNU FDL.