Direkt zum Inhalt

Lexikon der Mathematik: Chomsky-Hierarchie

Klassifikationsschema für formale Sprachen, dem die Struktur der Grammatik zur Erzeugung der jeweiligen Sprache zugrundeliegt.

Die Klassifikation erfolgt durch die Zuordnung der Sprache zu den Grammatik–Typen (Chomsky–Grammatik). Eine Sprache L ist vom Typ i, falls es eine Grammatik vom Typ i gibt, die L erzeugt. Die Nichtzugehörigkeit einer Sprache zu einer Klasse zeigt man oft mit Hilfe von Pumping-Lemmata.

Die Einordnung einer Sprache in die ChomskyHierarchie gibt Auskunft über die Verfügbarkeit von allgemeinen Analyseverfahren.

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.