Formale Sprache

Eine formale Sprache ist eine Menge von Zeichenketten endlicher Länge, die ein Alphabet endlicher Länge benutzen. Die Länge der Zeichenketten und die Länge des Alphabets ist endlich. Die Anzahl der Zeichenketten kann endlich oder unendlich sein.

Noam Chomsky hat eine Hierarchie von Sprachtypen von formalen Sprachen aufgestellt; sie ist heute unter dem Namen Chomsky-Hierarchie bekannt. Der einfachste Sprachtyp ist die sog. Reguläre Sprache. Mit ihr lassen sich Phänomene der Morphologie beschreiben. Reguläre Sprachen werden durch eine Anzahl reguläre Ausdrücke beschrieben.

Programmiersprachen sind formale Sprachen.