Like a Turing machine, an LBA possesses a tape made up of cells that can contain symbols from a finite alphabet, a head that can read from or write to one cell on the tape at a time and can be moved, and a finite number of states. Instead of having potentially infinite tape on which to compute, computation is restricted to the portion of the tape containing the input plus the two tape squares holding the endmarkers.Īn alternative, less restrictive definition is as follows: Its transitions may neither move to the left of the left endmarker nor to the right of the right endmarker. Its transitions may not print other symbols over the endmarkers. 
Its input alphabet includes two special symbols, serving as left and right endmarkers. OperationĪ linear bounded automaton is a nondeterministic Turing machine that satisfies the following three conditions: "Relationships between nondeterministic and deterministic tape complexities." Journal of computer and system sciences 4.2 (1970): 177-192.In computer science, a linear bounded automaton (plural linear bounded automata, abbreviated LBA) is a restricted form of Turing machine. If it is satisfactory then you may please give me an upvote. 
N.B: Please make me correct if I misunderstand the concepts. As an interesting aside, there remains an open problem to do with LBAs in the realm of complexity theory: does a deterministic LBA have the same power as a normal non-deterministic LBA or, equivalently, does NSPACE(n) = DSPACE(n)? So, this is all about a matter of storage, that is why we use NTM in the LBA as it requires less storage over DTM. Then Every context-sensitive language is accepted by some deterministic Turing machine within storage $n^2$. The context-sensitive languages are precisely those sets accepted by nondeterministic Turing machines within storage $L(n) = n$. Thus, in particular, every context-sensitive language can be recognized within deterministic storage $n^2$, where $n$ is the length of the input. A nondeterministic L(n)-tape bounded Turing machine can be simulated by a deterministic $^2$-tape bounded Turing machine, provided $L(n) \geq \log_2 n$.
0 kommentar(er)
