Unterabschnitte
Linear beschränkte Automaten sind NTMs, die mit linear beschränktem Platz auskommen. Sie sind durch zwei Begrenzungssymbole

und

links und rechts beschränkt.
Zu jeder kontextsensitiven Grammatik

gibt es einen LBA

mit
Zu jedem LBA

gibt es eine Grammatik

mit
Die Frage, ob deterministsche LBAs und nichtdeterministische LBAs die selben Sprachen akzeptieren können, ist noch nicht gelöst.
Der Algorithmus kann als nichtdeterministisches Zusammenschieben bezeichnet werden.
- Solange w
S
- Wähle nichtdeterministisch eine Regel
aus
.
- Wenn
ein Teilwort von
ist, ersetze es durch
.
- Schiebe den LBA um
Stellen zusammen. Das sind genau die Stellen, die nun nicht mehr benötigt werden.
- Wenn die Schleife erfolgreich abgelaufen ist, geben wir ,,JA'' aus.
Typ 1 Sprachen sind zusätzlich zu der Abgeschlossenheit von Typ 0 Sprachen auch unter dem
Komplement abgeschlossen.