In this section, we present a special, bounded version of the Turing machines, by which the class of context-sensitive languages can be characterized - as we already mentioned in Subsection. This version of the Turing machine can work only on the part of the tape where the input is/was. These automata are called linear bounded automata (LBA).

**Definition 36.**
*Let LBA* = (*Q, T, V, q*_{0}, *♯, δ, F*)
*be a Turing machine, where*

δ :

Q× (V \ {♯}) → 2^{Q}^{×}^{V}^{×{}^{Left, Right, Stay}^{}}

*and*

δ :

Q× {♯} → 2^{Q}^{×{}^{♯}^{}×{}^{Left, Right, Stay}^{}}.

*Then LBA is a (nondeterministic) linear bounded automaton.*

One can observe that ♯ signs cannot be rewritten to any other symbol, therefore, the automaton can store some results of its subcomputations only in the space provided by the input, i.e., in fact, the length of the input can be used during the computation, only.

**Example 59.** *Give an LBA that accepts the language*
{*a ^{i}b^{i}c^{i}*∣

*Solution:*

*Idea:*

*The automaton rewrites the first a to A, and changes its state, looks for the first b.**The automaton rewrites the first b to B, and changes its state, looks for the first c.**The automaton rewrites the first c to C, and changes its state, looks (backward) for the first a.**The capital letters A,B,C are read without changing them.**The above movements are repeated.**If finally only capital letters remain between the border ♯ signs, then the automaton accepts (the input).*

*Formally, let*

LBA= ({q_{0},q_{1},q_{2},q_{3},q_{4},q}, {_{f}a,b,c}, {a,b,c,A,B,C,♯},q_{0}, ♯, δ, {q})_{f}

*be a deterministic LBA, where δ consists of the next transitions: *

δ (

*q*_{0}, ♯) = (*q*, ♯,_{f}*Right*) –*the empty word is accepted by LBA.*δ (

*q*_{0},*a*) = (*q*_{1},*A, Right*) –*the first (leftmost) a is rewritten to A and LBA changes its state.*δ (

*q*_{0},*B*) = (*q*_{0},*B, Left*) –*the capital letters B and C are skipped in state q*_{0},δ (

*q*_{0},*C*) = (*q*_{0},*C, Left*) –*by moving the head to the left.*δ (

*q*_{1},*a*) = (*q*_{1},*a, Right*) –*letter a is skipped in state q*_{1}*to the right.*δ (

*q*_{1},*B*) = (*q*_{1},*B, Right*) –*capital B is also skipped.*δ (

*q*_{1},*b*) = (*q*_{2},*B, Right*) –*the leftmost b is rewritten by B and the state becomes q*_{2}.δ (

*q*_{2},*b*) = (*q*_{2},*b, Right*) –*letter b is skipped in state q*_{2}*to the right.*δ (

*q*_{2},*C*) = (*q*_{2},*C, Right*) –*capital C is also skipped in this state.*δ (

*q*_{2},*c*) = (*q*_{3},*C, Left*) –*the leftmost c is rewritten by C and LBA changes its state to q*_{3}.δ (

*q*_{3},*a*) = (*q*_{3},*a, Left*) –*letters a,b are skipped in state q*_{3}δ (

*q*_{3},*b*) = (*q*_{3},*b, Left*) –*by moving the head of the automaton to the left.*δ (

*q*_{3},*C*) = (*q*_{3},*C, Left*) –*capital letters C,B are skipped in state q*_{3}δ (

*q*_{3},*B*) = (*q*_{3},*B, Left*) –*by moving the head of the automaton to the left.*δ (

*q*_{0},*A*) = (*q*_{3},*A, Right*) –*the head is positioned after the last A and the state is changed to q*_{0}.δ (

*q*_{4},*B*) = (*q*_{3},*B, Right*) –*if there is a B after the last A the state is changed to q*_{4}.δ (

*q*_{4},*B*) = (*q*_{4},*B, Right*) –*in state q*_{4}*capital letters B and C are skipped*δ (

*q*_{4},*C*) = (*q*_{4},*C, Right*) –*by moving the head to the right.*δ (

*q*,_{f}*♯*) = (*q*_{4},*♯, Left*) –*if in q*_{4}*there were only capital letters on the tape, LBA accepts.*

*The work of the automaton can be described as follows: it is clear by transition 1, that λ is accepted. *

*Otherwise the head reads the first letter of the input: if the input starts with an a, then it is replaced by A
and q*_{1} *is the new state.
If the first letter of the input is not a, then LBA gets stuck, i.e., it is halting without acceptance, since there are no defined transitions in
this state for the other input letters. *

*In state q*_{1} *LBA looks for the first b by moving to the right (skipping every a and B, if any;
and halting without acceptance by
finding other letters before the first b). When a b is found it is rewritten to a B and the automaton changes its state to q*_{2}.

*In q*_{2} *the first c is searched, the head can move through on b's and C's (but not on other letters)
to the right.
When it finds a c it rewrites by a C and changes the state to q3 and starts to move back to the left.*

*In q*_{3} *the head can go through on letters a,B,b,C to the left and when finds an A it steps to the right
and the state becomes q*_{0}. *In q*_{0}
*if there is an a under the head, then it is rewritten by an A and the whole loop starts again. *

*If in q*_{0} *a letter B is found (that could happen when every a is rewritten by an A already),
LBA changes its state to q*_{4}.
*In this state by stepping to the right LBA checks if every b and c is already rewritten and if so, i.e., their number
is the same as the number of a's and their order was correct (the input is in the
language a ^{*}b^{*}c^{*}), then LBA reaches the marker ♯
sign after the input and accepts.*

*When at any stage some other letter is being read than it is expected (by the previous description),
then LBA halts without accepting the input.*

*Thus, the accepted language is exactly*
{*a ^{i}b^{i}c^{i}*∣

To establish a connection between the classes of context-sensitive languages and linear bounded automata we present the following theorem.

**Theorem 46.**
*The class of languages accepted by linear bounded automata and the class of context-sensitive languages coincide.*

**Proof.** We do not give a formal proof here, instead we present the idea of a proof.
A context-sensitive language can be defined by a monotone grammar. In a monotone grammar (apart from the derivation of the empty word, if it is in the language),
the length of the sentential form cannot be decreased by any step of the derivation.
Consequently, starting from the derived word, and applying the rules in a way which is an inverse, the length is monotonously decreasing
till we obtain the start symbol. In this way every context-sensitive language can be accepted by an LBA.

The other way around, the work of an LBA can be described by a grammar, working in inverse way of the generation
(starting from a word the start symbol is the target). These grammars are similar to the previously used monotone grammars,
and thus, if an LBA is accepting a language *L*, then *L* is context-sensitive.

QED.

Actually, there are other models of LBA, in which the workspace (the maximal tape-length during the computation) is limited
by *c*_{1} · ∣w∣ + *c*_{0},
where *w* is the input and *c*_{0}, *c*_{1} ∈ ℝ constants.
The accepting power of these models are the same as of those that have been presented.

However, the deterministic model is more interesting, since it is related to a long-standing and still open question.

It is known that every context-sensitive language can be accepted by deterministic Turing machines, using at most
*c*_{2}· ∣w∣^{2} + *c*_{1} · ∣w∣
+ *c*_{0} space during the computations, where *c*_{2},
*c*_{1}, *c*_{0} are constants.
However, it is neither proven nor disproved that deterministic linear bounded automata (using
*c*_{1} · ∣w∣ + *c*_{2} space)
can recognize every context-sensitive language. This is still a *famous* open problem.

**Exercise 85.**
*Give a linear bounded automaton that accepts the language*

{

a∣^{i}b^{j}a^{i}b^{j}i, j∈ ℕ}.

**Exercise 86.**
*Give a linear bounded automaton that accepts the language*

{

a^{2}∣^{i}i∈ ℕ},

i.e., the language of powers of two in unary coding.

**Exercise 87.**
*Give a linear bounded automaton that accepts the set of primitive words over the alphabet* {*a,b*}.
*(A word w is primitive if it is not of the form u ^{n} for any word u≠ w.)*