linear-bounded automaton (LBA)

A linear-bounded automaton (LBA) is a type of computational model used in formal language theory. It is similar to a Turing machine but has a restriction: it can only use tape space proportional to the input size, meaning it cannot expand its working area beyond a linear function of the input length. This constraint makes LBAs capable of recognizing context-sensitive languages—more complex than those recognized by simpler automata but less than general Turing machines. In essence, an LBA processes input within a limited space that grows linearly with the input, enabling it to analyze certain structured language patterns efficiently.