Die Chomsky-Hierarchie

Die Chomsky-Hierarchie ordnet formale Sprachen in vier verschachtelte Klassen, die jeweils durch eine Einschränkung der Grammatikregeln definiert und einem bestimmten Typ abstrakter Maschine zugeordnet sind.

Definition

Die Chomsky-Hierarchie ist eine Klassifikation formaler Grammatiken durch progressiv stärkere Einschränkungen ihrer Produktionsregeln, die die regulären, kontextfreien, kontextsensitiven und rekursiv aufzählbaren Sprachklassen in einer Kette strikter Inklusionen hervorbringt.

Scope

Dieses Thema behandelt die vier Grammatiktypen – unbeschränkt, kontextsensitiv, kontextfrei und regulär – ihre strikte Inklusion und das Automatenmodell, das jeder Ebene entspricht, nämlich die Turingmaschine, den linear beschränkten Automaten, den Kellerautomaten und den endlichen Automaten, zusammen mit den Abschluss- und Entscheidbarkeitseigenschaften, die die Ebenen trennen.

Core questions

• Wie übersetzen sich Einschränkungen von Grammatikregeln in Grenzen der Speicher- und Rechenleistung?
• Warum ist jede Ebene der Hierarchie strikt in der nächsten enthalten?
• Welches Automatenmodell entspricht welchem Grammatiktyp?
• Wie ändern sich Entscheidbarkeits- und Abschlusseigenschaften, wenn man die Hierarchie aufsteigt?

Key theories

Grammatik-Maschinen-Korrespondenz

Jede Grammatikklasse wird von einem spezifischen Maschinenmodell erkannt – reguläre durch endliche Automaten, kontextfreie durch Kellerautomaten, kontextsensitive durch linear beschränkte Automaten und unbeschränkte durch Turingmaschinen – wodurch generative und operationale Beschreibungen der Berechnung verknüpft werden.

Strikte Inklusion der Sprachklassen

Jede Ebene enthält die darunter liegende Ebene ordnungsgemäß, belegt durch konkrete trennende Sprachen, sodass die Hierarchie eine echte Leiter zunehmender Ausdruckskraft und nicht eine Sammlung äquivalenter Beschreibungen ist.

Clinical relevance

Die Hierarchie ist die ordnende Karte der formalen Sprachtheorie: Sie zeigt Designern von Programmiersprachen, Abfragesprachen und Protokollspezifikationen, wie viel Maschinerie eine gegebene Klasse von Mustern erfordert, und sie umreißt die Grenze zwischen dem, was entscheidbar ist, und dem, was nur erkennbar ist.

History

Chomsky schlug die Hierarchie in den späten 1950er Jahren vor, als er formale Modelle der Syntax natürlicher Sprachen suchte, und die Maschinenkorrespondenzen wurden etabliert, als die Automatentheorie in den 1960er Jahren reifte, wobei linear beschränkte Automaten von Myhill eingeführt und die kontextsensitive Ebene von Kuroda präzisiert wurden.

Key figures

• Noam Chomsky
• Marcel-Paul Schützenberger
• John Myhill

Seminal works

• hopcroft2006
• sipser2013

Frequently asked questions

Was sind die vier Ebenen der Chomsky-Hierarchie?

Von der geringsten zur größten Mächtigkeit sind dies reguläre Sprachen (Typ 3), kontextfreie Sprachen (Typ 2), kontextsensitive Sprachen (Typ 1) und rekursiv aufzählbare Sprachen (Typ 0). Jede Ebene lockert die Einschränkungen der Grammatikregeln und entspricht einer Maschine mit mehr Speicher.

Wird die natürliche Sprache von der Chomsky-Hierarchie erfasst?

Die Hierarchie wurde ursprünglich durch die Linguistik motiviert, aber die meisten Linguisten kommen zu dem Schluss, dass natürliche Sprachen nicht kontextfrei sind und sich auf einer Ebene befinden, die oft als mild kontextsensitiv bezeichnet wird. Die Hierarchie bleibt in der Informatik grundlegend, auch wenn die menschliche Sprache nur lose dazu passt.