Die nutzbare Bandlänge ist dann also linear in der Länge der Eingabe. Dies erklärt das "Linear" im Namen der LBA. Die von nichtdeterministischen LBAs akzeptierten Sprachen sind genau die kontextsensitiven Sprachen (vgl. Chomsky-Hierarchie). Es ist ein offenes Problem, ob deterministische LBAs die gleiche Sprachklasse akzeptieren wie die nicht.....