Direkt zum Inhalt

Lexikon der Mathematik: nichtdeterministischer linear beschränkter Akzeptor

NLBA, in ihrer Funktion eingeschränkte nichtdeterministische Turing-Maschine mit einem Band und einem Schreib/Lese-Kopf.

Die Einschränkung besteht darin, daß als Kopfposition nur diejenigen Bandfelder zulässig sind, die eingangs mit der Eingabe der Maschine beschriftet waren. Die Einschränkung läßt sich realisieren, indem die Eingabe durch zwei den linken bzw. rechten Rand kennzeichnende Sonderzeichen begrenzt wird, die als Reaktion eine Kopfbewegung nach rechts (linker Rand) bzw. links (rechter Rand) ohne Überschreiben der Sonderzeichen erzwingen.

Zu einer Sprache gibt es genau dann einen nichtdeterministischen linear beschränkten Akzeptor, wenn sie eine kontextsensitive Grammatik besitzt.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos