Kontextsensitive Sprachen - Typ 1 ::: Theoretische Informatik

Linear beschränkte Automaten sind NTMs, die mit linear beschränktem Platz auskommen. Sie sind durch zwei Begrenzungssymbole $\$$ und $\char93$ links und rechts beschränkt.
Zu jeder kontextsensitiven Grammatik

gibt es einen LBA $\tau$ mit

$\begin{displaymath}L_{LBA}(\tau)=L(G)\end{displaymath}$

Zu jedem LBA $\tau$ gibt es eine Grammatik

mit

$\begin{displaymath}L(G)=L_{LBA}(\tau)\end{displaymath}$

Determinismus $\leftrightarrow$ Nichtdeterminismus

Die Frage, ob deterministsche LBAs und nichtdeterministische LBAs die selben Sprachen akzeptieren können, ist noch nicht gelöst.

Wortproblem

Der Algorithmus kann als nichtdeterministisches Zusammenschieben bezeichnet werden.

Solange w S
- Wähle nichtdeterministisch eine Regel $u\rightarrow v$ aus .
- Wenn ein Teilwort von ist, ersetze es durch .
- Schiebe den LBA um $\vert v\vert-\vert u\vert$ Stellen zusammen. Das sind genau die Stellen, die nun nicht mehr benötigt werden.
Wenn die Schleife erfolgreich abgelaufen ist, geben wir ,,JA'' aus.