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.

  • Die Autoren
- Prof. Dr. Guido Walz

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.

Partnerinhalte

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