Linear Bounded Automata

Question

In LBA why not tape length same as input length? Why tape length linear multiple of input length? Why not it non linear?

Comments

Because that is the definition of LBA. An LBA is a turing machine which has the tape length linearly proportional to the input string length. that is why it is called a "LINEAR" - "BOUNDED" automata.

---

but it is not same as input length. It is always linear multiple, describe this part

---

I think it can be same as input length. I studied from peter Linz.

---

LBA tape length can be same as input length...the only restriction is they should be bounded in linear manner...in that way they are just equivalent to our computers because unlike TM, our computer can't have infinite memory...LBA are linear so they they can be simulated to other LBAs that corresponds to tape size same as input...

https://www.seas.upenn.edu/~cit596/notes/dave/chomsky2.html

Answer 1

As per Peter Linz

 “We allow the machine to use only that part of the tape occupied by the input. Thus, more space is available for long input strings than for short ones, generating another class of machines, the linear bounded automata (or lba). A linear bounded automaton, like a standard Turing machine, has an unbounded tape, but how much of the tape can be used is a function of the input. In particular, we restrict the usable part of the tape to exactly the cells taken by the input.1 To enforce this, we can envision the input as bracketed by two special symbols, the left-end marker [ and the right-end marker ]. For an input w, the initial configuration of the Turing machine is given by the instantaneous description q0 [w]. The end markers cannot be rewritten, and the read-write head cannot move to the left of [ or to the right of ]. We sometimes say that the read-write head “bounces” off the end markers.”