Unterabschnitte
Linear beschränkte Automaten sind NTMs, die mit linear beschränktem Platz auskommen. Sie sind durch zwei Begrenzungssymbole
![$\$ $](img443.png)
und
![$\char93 $](img444.png)
links und rechts beschränkt.
Zu jeder kontextsensitiven Grammatik
![$G$](img402.png)
gibt es einen LBA
![$\tau$](img64.png)
mit
Zu jedem LBA
![$\tau$](img64.png)
gibt es eine Grammatik
![$G$](img402.png)
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.