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.