Innerhalb des Feldes der Informatik, spezifisch im Gebiet von formellen Sprachen, ist die Hierarchie von Chomsky (gelegentlich gekennzeichnet als Hierarchie von Chomsky-Schützenberger) eine Eindämmungshierarchie von Klassen von formellen Grammatiken.

Diese Hierarchie von Grammatiken wurde von Noam Chomsky 1956 beschrieben. Es wird auch nach Marcel-Paul Schützenberger genannt, der eine entscheidende Rolle in der Entwicklung der Theorie von formellen Sprachen gespielt hat.

Formelle Grammatiken

Eine formelle Grammatik dieses Typs besteht aus:

• ein begrenzter Satz von Produktionsregeln (linke Seitenrechte), wo jede Seite aus einer Folge dieser Symbole besteht
• ein begrenzter Satz von Endsymbolen (die in der linken Seite keiner Produktionsregel erscheinen)
• ein begrenzter Satz von Nichtendsymbolen (die in der linken Seite keiner Produktionsregel erscheinen)
• ein Anfang-Symbol

Eine formelle Grammatik definiert (oder erzeugt) eine formelle Sprache, die (gewöhnlich unendlich) Satz von Folgen der begrenzten Länge von Symbolen ist (d. h. Schnuren), der durch die Verwendung von Produktionsregeln auf eine andere Folge von Symbolen gebaut werden kann, die am Anfang gerade das Anfang-Symbol enthält. Eine Regel kann auf eine Folge von Symbolen durch das Ersetzen eines Ereignisses der Symbole auf der linken Seite der Regel mit denjenigen angewandt werden, die auf der rechten Seite erscheinen. Eine Folge von Regel-Anwendungen wird eine Abstammung genannt. Solch eine Grammatik definiert die formelle Sprache: Alle Wörter, die allein aus Endsymbolen bestehen, die durch eine Abstammung vom Anfang-Symbol erreicht werden können.

Nichtterminals werden gewöhnlich durch Großbuchstaben, Terminals durch Kleinbuchstaben und das Anfang-Symbol dadurch vertreten. Zum Beispiel, die Grammatik mit Terminals, Nichtterminals, herrscht Produktion

über:

: ε (wo ε ist die leere Schnur)

:::::

und fangen Sie Symbol an, definiert die Sprache aller Wörter der Form (d. h. Kopien von gefolgten von Kopien).

Der folgende ist eine einfachere Grammatik, die dieselbe Sprache definiert:

Terminals, Nichtterminals, Anfang-Symbol, herrscht Produktion

über:

:

ε

Die Hierarchie

Die Hierarchie von Chomsky besteht aus den folgenden Niveaus:

• Grammatiken des Typs 0 (uneingeschränkte Grammatiken) schließen alle formellen Grammatiken ein. Sie erzeugen genau alle Sprachen, die durch eine Maschine von Turing anerkannt werden können. Diese Sprachen sind auch bekannt als rekursiv enumerable Sprachen. Bemerken Sie, dass das von den rekursiven Sprachen verschieden ist, die durch eine immer stockende Maschine von Turing entschieden werden können.
• Grammatiken des Typs 1 (mit dem Zusammenhang empfindliche Grammatiken) erzeugen die mit dem Zusammenhang empfindlichen Sprachen. Diese Grammatiken haben Regeln der Form mit einem Nichtterminal und, und Reihen von Terminals und Nichtterminals. Die Schnuren und können leer sein, aber müssen nichtleer sein. Der Regel wird erlaubt, wenn auf der richtigen Seite keiner Regel erscheint. Die durch diese Grammatiken beschriebenen Sprachen sind genau alle Sprachen, die durch einen geradlinigen begrenzten Automaten anerkannt werden können (eine nichtdeterministische Maschine von Turing, deren Band durch eine Konstante Zeiten die Länge des Eingangs begrenzt wird.)
• Grammatiken des Typs 2 (Grammatiken ohne Zusammenhänge) erzeugen die Sprachen ohne Zusammenhänge. Diese werden durch Regeln der Form mit einem Nichtterminal und einer Reihe von Terminals und Nichtterminals definiert. Diese Sprachen sind genau alle Sprachen, die durch einen nichtdeterministischen pushdown Automaten anerkannt werden können. Sprachen ohne Zusammenhänge sind die theoretische Basis für die Syntax von den meisten Programmiersprachen.
• Grammatiken des Typs 3 (regelmäßige Grammatiken) erzeugen die regelmäßigen Sprachen. Solch eine Grammatik schränkt seine Regeln auf ein einzelnes Nichtterminal auf der linken Seite und eine Rechte ein, die aus einem einzelnen Terminal, vielleicht gefolgt besteht (oder ist vorangegangen, aber nicht beide in derselben Grammatik) durch ein einzelnes Nichtterminal. Der Regel wird auch hier erlaubt, wenn auf der richtigen Seite keiner Regel erscheint. Diese Sprachen sind genau alle Sprachen, die durch einen Zustandsautomaten entschieden werden können. Zusätzlich kann diese Familie von formellen Sprachen durch regelmäßige Ausdrücke erhalten werden. Regelmäßige Sprachen werden allgemein verwendet, um Suchmuster und die lexikalische Struktur von Programmiersprachen zu definieren.

Bemerken Sie, dass der Satz von Grammatiken entsprechend rekursiven Sprachen nicht ein Mitglied dieser Hierarchie ist.

Jede regelmäßige Sprache ist ohne Zusammenhänge, jede Sprache ohne Zusammenhänge, die leere Schnur nicht enthaltend, ist mit dem Zusammenhang empfindlich, und jede mit dem Zusammenhang empfindliche Sprache ist rekursiv, und jede rekursive Sprache ist rekursiv enumerable. Das sind alle richtigen Einschließungen, bedeutend, dass dort rekursiv enumerable Sprachen bestehen, die nicht mit dem Zusammenhang empfindliche, mit dem Zusammenhang empfindliche Sprachen sind, die nicht Sprachen ohne Zusammenhänge ohne Zusammenhänge sind, die nicht regelmäßig sind.

Der folgende Tisch fasst jeden von vier Typen von Chomsky von Grammatiken, der Klasse der Sprache zusammen, die es, der Typ des Automaten erzeugt, der es, und die Form anerkennt, die seine Regeln haben müssen.

Jedoch gibt es weitere Kategorien von formellen Sprachen, von denen einige im folgenden Tisch gegeben werden:

Links

http://www.staff.ncl.ac.uk/hermann.moisl/ell236/lecture5.htm

• "Ist chomsky Hierarchie überholt/6133" auf cstheory.stackexchange.com