linear bounded automaton
A linear bounded automaton, or LBA for short, is a restricted form of a nondeterministic Turing machine with a single tape and a single tape head, such that, given an input word on the tape, the tape head can only scan and rewrite symbols on the cells occupied by the initial input word.
Formally, a linear bounded automaton is a 9tuple $M=(Q,\mathrm{\Sigma},\mathrm{\Gamma},\delta ,{q}_{0},B,F,\mathrm{\backslash Yleft},\mathrm{\backslash Yright})$, where

1.
$Q$ is the state alphabet

2.
$\mathrm{\Sigma}$ is the input alphabet

3.
$\mathrm{\Gamma}$ is the tape alphabet and $\mathrm{\Sigma}\subset \mathrm{\Gamma}$

4.
$\mathrm{\backslash Yleft},\mathrm{\backslash Yright}\in \mathrm{\Sigma}$ are the left and right end markers.

5.
$\delta $ is a function from $Q\times \mathrm{\Gamma}$ to $P(Q\times \mathrm{\Gamma}\times \{L,R\})$, called the next move function

6.
${q}_{0}\in Q$ is the start state

7.
$B\in \mathrm{\Gamma}\mathrm{\Sigma}$ is the blank symbol

8.
$F\subset Q$ is the set of final states
The interpretation^{} of $(q,b,D)\in \delta (p,a)$ is the same as that of a nondeterministic TM: if the $M$ is in state $p$ and the tape head is reading a tape cell containing $a$, then it replaces $a$ by $b$ in that tape cell, and move in the direction of $D$ ($D=L$ for left, and $D=R$ for right), and changes its state to $q$. In addition^{}, the next move function $\delta $ has the following properties:

•
if $(q,b,D)\in \delta (p,\mathrm{\backslash Yleft})$, then $b=\mathrm{\backslash Yleft}$ and $D=R$, and

•
if $(q,b,D)\in \delta (p,\mathrm{\backslash Yright})$, then $b=\mathrm{\backslash Yright}$ and $D=L$.

•
if $(q,b,D)\in \delta (p,a)$ and $a\notin \{\mathrm{\backslash Yleft},\mathrm{\backslash Yright}\}$, then $b\notin \{\mathrm{\backslash Yleft},\mathrm{\backslash Yright}\}$.
In other words, if the tape head is reading the left end marker $\mathrm{\backslash Yleft}$, then if it has a next move, it can only move right without replacing the end marker $\mathrm{\backslash Yleft}$. Similarly, if it is reading the right end marker $\mathrm{\backslash Yright}$, then it can only move left if it has any next move at all, without replacing $\mathrm{\backslash Yright}$. Furthermore, no symbol can be replaced by an end marker unless the symbol itself is the end marker.
An LBA is also known as a nondeterministic LBA, or NLBA for short. An LBA is said to be deterministic^{} (abbreviated as DLBA) if $\delta (p,a)$ is at most a singleton for every pair $(p,a)\in Q\times \mathrm{\Gamma}$.
A configuration of $M$ is a triple $(p,u,i)$, where $p\in Q$ is the current state of $M$, $u\in \{\mathrm{\backslash Yleft}\}{\mathrm{\Gamma}}^{*}\{\mathrm{\backslash Yright}\}$ is the content of the tape (including the end markers), and $i$ a nonnegative integer, the position of the tape head, where $i=0$ is the position of $\mathrm{\backslash Yleft}$, the left end marker.
Define a binary relation^{} $\Rightarrow $ on the set of all configurations of $M$: for ${a}_{i},b\in \mathrm{\Gamma}$,
$$(p,{a}_{0}\mathrm{\cdots}{a}_{i1}a{a}_{i+1}\mathrm{\cdots}{a}_{n+1},i)\Rightarrow (q,{a}_{0}\mathrm{\cdots}{a}_{i1}b{a}_{i+1}\mathrm{\cdots}{a}_{n+1},j),$$ 
where $i=1,\mathrm{\dots},n$ and $n$ a nonnegative integer, iff any one of the following holds:
$$(q,b,L)\in \delta (p,{a}_{i})\text{and}j=i1\mathit{\hspace{1em}\hspace{1em}}\text{or}\mathit{\hspace{1em}\hspace{1em}}(q,b,R)\in \delta (p,{a}_{i})\text{and}j=i+1.$$ 
Notice that ${a}_{0}=\mathrm{\backslash Yleft}$ and ${a}_{n+1}=\mathrm{\backslash Yright}$. If $i=0$, then the former case can not happen, and if $i=n+1$, then the latter case can not happen.
Take the reflexive transitive closure ${\Rightarrow}^{*}$ of $\Rightarrow $, and set
$$L(M):=\{u\in {\mathrm{\Sigma}}^{*}\mid ({q}_{0},\mathrm{\backslash Yleft}u\mathrm{\backslash Yright},0){\Rightarrow}^{*}(q,\mathrm{\backslash Yleft}v\mathrm{\backslash Yright},j)\text{for some}q\in F\}$$ 
the language^{} accepted by $M$.
Remarks

•
For a given input word $u$, the workspace $w(u)$ of an LBA is defined as the portion of the tape between the end markers (including the end markers). In the definition above, we see that $w(u)=u+2$, where $\cdot $ is the length function. One can enlarge the workspace so that $w(u)=ru+s$, where $r,s$ are positive integers with $r\ge 1$ and $s\ge 2$. This is the reason for the name “linear bounded” in LBA. However, the computational power of an LBA with enlarged workspace is not increased: the language accepted by such an LBA can be accepted by an LBA defined above.

•
A language is contextsensitive iff it can be accepted by an LBA.

•
Every contextfree language can be accepted by a DLBA, but not conversely.

•
It is an open question whether every contextsensitive language can be accepted by a DLBA.
References
 1 J.E. Hopcroft, J.D. Ullman, Formal Languages^{} and Their Relation^{} to Automata, AddisonWesley, (1969).
Title  linear bounded automaton 
Canonical name  LinearBoundedAutomaton 
Date of creation  20130322 18:57:40 
Last modified on  20130322 18:57:40 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  10 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 68Q45 
Synonym  LBA 
Synonym  NLBA 
Synonym  DLBA 
Synonym  deterministic LBA 
Related topic  ContextSensitiveGrammar 
Related topic  ContextSensitiveLanguage 
Defines  deterministic linear bounded automaton 