Sprachklasse
Unter einer Sprachklasse versteht man in Linguistik und Informatik eine Menge von Sprachen, die über einem gegebenen Alphabet gebildet werden können. Eine Sprache ist dabei eine Menge von Worten über diesem Alphabet, und ein Alphabet ist eine (normalerweise endliche) Menge von Zeichen oder Symbolen.
Der amerikanische Publizist und Sprachtheoretiker Noam Chomsky hat die von intelligenten Wesen erkennbaren oder klassifizierbaren Sprachen in vier abstrakte Klassen aufgeteilt und damit die formalen Grundlagen für die theoretische Informatik gelegt und einen wesentlichen Beitrag zur mathematischen Logik geleistet. Grundlage der Klassifizierung von Sprachen ist ein Ersetzungs- und ein Korrespondenzprinzip, welches abgestuft zu den Klassen CH(0) bis CH(3) führt. Diese formalen Sprachklassen umfassen die mathematische Logik, mathematische Algebra und alle weiteren von Menschen erdachten Kalküle.
Sprachklassen können durch die Angabe formaler Grammatiken, durch Automaten oder durch Anwendung von Operationen auf (bereits bekannten) Sprachklassen definiert werden. Sie haben ihr Pendant in den Automatenmodellen, ähnlich wie sich Software zu Hardware verhält.
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
- - die Menge aller Sprachen
Siehe auch
Literatur
- Werner Ebinger: Charakterisierung von Sprachklassen unendlicher Spuren durch Logiken. Diss., Universität Stuttgart, 1994.