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
Schreiben Sie uns!