Chomsky-Hierarchie

Chomsky-Hierarchie, gelegentlich Chomsky-Schützenberger-Hierarchie (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger), ist ein Begriff aus der Theoretischen Informatik. Sie ist eine Hierarchie von Klassen formaler Grammatiken, die formale Sprachen erzeugen, und wurde 1956 erstmals von Noam Chomsky beschrieben. Die Hierarchiestufen unterscheiden sich darin, wie rigide die Einschränkungen für die Form zulässiger Produktionsregeln auf der jeweiligen Stufe sind; bei Typ-0-Grammatiken sind sie uneingeschränkt, bei höheren Stufen fortschreitend stärker beschränkt. Grammatiken niedrigeren Typs sind erzeugungsmächtiger als die höherer Typen. Eine Sprache, die von einer Grammatik des Typs k erzeugt wird, heißt eine Sprache des Typs k. Neben die Chomsky-Hierarchie der Grammatiken tritt in diesem Sinne eine Chomsky-Hierarchie der Sprachen. Siehe auch: Generative Transformationsgrammatik