Benutzer:Kleinvieh macht auch Mist/Chomsky-Hierarchie

Ich habe vor den Artikel der Chomsky-Hierarchie zu überarbeiten, und diese Seite dient mir als Hilfe. Hier werden erste Entwürfe und Zwischenergebnisse zu sehen sein.

Bitte nutzt die Diskussionsseite und ändert hier nichts!

zum Artikel vor den umfassenden Änderungen

Chomsky-Hierarchie (Aktuelle Überlegungen)

Chomsky-Hierarchie ist ein Begriff aus der Theoretischen Informatik und bezeichnet eine Hierarchie von Klassen formaler Grammatiken, mit deren Hilfe formale Sprachen erzeugt werden können. Sie wurde 1956 von Noam Chomsky beschrieben.

Bla (Überschrift wird noch gesucht)

Die vier von Chomsky beschriebenen Grammatiktypen entstehen dabei ausgehend von einer nicht eingeschränkten Grundgrammatik (der Typ-0-Grammatik) dergestalt, dass zunehmend Einschränkungen bezüglich der für den Typ erlaubten Produktionsregeln gemacht werden. Jede Grammatik höheren Typs ist also ein Speziallfall (eine echte Teilmenge) einer Grammatik niederen Typs:

Typ-3-Grammatik $\subset$ Typ-2-Grammatik $\subset$ Typ-1-Grammatik $\subset$ Typ-0-Grammatik

Jede Typ-1-Grammatik ist also auch eine Typ-0-Grammatik, aber nicht jede Typ-1-Grammatik ist auch eine Typ-2-Grammatik.

Entsprechend dem Typ einer Grammatik, die mindestens erforderlich ist, um eine bestimmte formale Sprache zu erzeugen, werden auch formale Sprachen in dieselben Kategorien von Typen eingeteilt. Eine formale Sprache heißt Typ-$i$-Sprache (mit $i=0,1,2,3$), wenn sie von einer Grammatik vom Typ $i$ erzeugt werden kann.

Übersicht

Die folgende Tabelle fasst für die vier Klassen der Chomsky-Hierarchie die Grammatiken, die erzeugten Sprachen und die Automatentypen, die sie erkennen, zusammen.

--Bis hierher erst einmal! Kleinvieh 21:49, 6. Dez 2005 (CET)