Satz von Kuroda

Die von linear beschränkten Turing-Maschinen akzeptierbaren Sprachen sind genau die kontextsensitiven Sprachen

Erweiterung

Die durch allgemeine Turing-Maschinen akzeptierbaren Sprachen sind genau die Phasenstruktursprachen

Siehe auch

• Chomsky-Hierachie