Die Chomsky-Hierarchie ist eine Einteilung der Menge aller Sprachen in verschiedene (absteigend) mächtige Klassen. Folgende Beschränkungen werden allen Regeln der Form
| Grammatiktyp | Regelformat | Erkennende Instanzen |
|---|---|---|
| Typ 0 ( Phasenstruktur-grammatiken | Keine Regeleinschränkungen, enthält (per Definition) jede Grammatik | Turing-Maschine |
| Typ 1 ( Kontextsensitive Grammatiken | Linear beschränkte Turing-Maschine | |
| Typ 2 ( Kontextfreie Grammatiken | Kellerautomat | |
| Typ 3 ( Reguläre Grammatiken Auch Rechtslinear genannt | Deterministischer Endlicher Automat, Nichtdeterministischer Endlicher Automat, Reguläre Ausdrücke |
Erbung der Beschränkungen
Für Typ
-Grammatiken gelten jeweils die Beschränkungen von Typ -Grammatiken.
Transclude of sonderregel-für-leeres-wort#^Sonderregel
Siehe auch