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.
Copyright Springer Verlag GmbH Deutschland 2017
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.