Sprachklasse

Grundbegriff

Eine Sprachklasse ist in Linguistik und Informatik eine Menge von Sprachen, die über einem gegebenen Alphabet gebildet werden können. Eine Sprache ist eine Menge von Worten über diesem Alphabet. Ein Alphabet ist eine normalerweise endliche Menge von Zeichen oder Symbolen.

Sprachklassen sind wichtig, weil sie formale Sprachen nach ihren Eigenschaften ordnen. Dadurch lassen sich Sprachen mathematisch beschreiben und mit passenden Modellen der Informatik untersuchen.

Chomsky-Klassifikation

Noam Chomsky teilte die von intelligenten Wesen erkennbaren oder klassifizierbaren Sprachen in vier abstrakte Klassen ein. Diese Einteilung legte formale Grundlagen für die theoretische Informatik und leistete einen Beitrag zur mathematischen Logik.

Die Klassifizierung beruht auf einem Ersetzungsprinzip und einem Korrespondenzprinzip. Daraus entstehen abgestuft die Klassen CH(0) bis CH(3). Diese formalen Sprachklassen umfassen die mathematische Logik, mathematische Algebra und weitere von Menschen erdachte Kalküle.

Beschreibung von Sprachklassen

Sprachklassen können auf verschiedene Weise definiert werden: durch formale Grammatiken, durch Automaten oder durch Operationen auf bereits bekannten Sprachklassen.

Zu den Sprachklassen gibt es passende Automatenmodelle. Das Verhältnis wird im Artikel mit dem Verhältnis von Software zu Hardware verglichen: Die Sprachklasse beschreibt die formale Ebene, das Automatenmodell die entsprechende Modellierung durch einen Automaten.

Bekannte Klassen

Bekannte Sprachklassen sind:

• 3: die Menge der regulären Sprachen.
• 2: die Menge der kontextfreien Sprachen.
• 1: die Menge der kontextsensitiven Sprachen.
• 0: die Menge der rekursiv aufzählbaren Sprachen.
• Außerdem: die Menge aller Sprachen.