Linear Bounded Automata (LBA): Definition, Tape Restriction, and an LBA for $\\{a^n b^n c^n\\}$

A Linear Bounded Automaton (LBA) is a Turing-machine model whose computation is memory-bounded: on an input string $w$ of length $n$, the automaton is allowed to use only a tape segment of size at most linear in $n$. This “linear boundedness” is what makes LBAs capture exactly the class of context-sensitive languages.

Intuitively, the LBA can still move the head and rewrite symbols, but it cannot use more than $O(n)$ tape cells. Formally, if the input length is $n$, there exists a constant $k$ such that the machine may not visit tape cells outside a segment of length $k n$ (equivalently, it cannot require more than $k n$ working tape space). This restriction is the key difference between an LBA and an unrestricted Turing machine, and it is what prevents “too much workspace” for the machine to decide arbitrary languages.

Context-sensitive languages (CSL) and LBAs are tightly connected: LBAs recognize precisely the CSL class. This connection is standard in automata theory texts and is commonly presented via the equivalence between LBAs and context-sensitive grammars (details depend on the specific variant of the formal model).

Tape length restriction: what “linear bounded” means

Let the input be $w$ with $|w|=n$. An LBA is a Turing-machine-like device where there is a fixed linear bound on how far the head can go from the input region. A typical formal statement is:

• the tape is conceptually infinite, but
• for every input of length $n$, the machine is constrained to operate only within some tape interval whose size is $\le k n$ for a constant $k$ independent of the input.

So the machine cannot “grow” its used tape capacity beyond a linear function of input size. This restriction is exactly what yields the recognition power of context-sensitive languages rather than the full power of general Turing machines.

Working tape in an LBA is therefore limited to $O(n)$ cells. If the machine tried to access a cell outside that bounded region, its computation would be deemed invalid (or it would halt/reject depending on the formal convention used).

Target language

We design an LBA for:

$L=\{a^n b^n c^n \mid n\ge 1\}.$

This language is context-sensitive (and thus recognizable by an LBA), but it is not context-free. The LBA construction will follow the standard “match counts using marked symbols” idea, while ensuring the machine never uses more than $O(n)$ tape cells.

Key idea:

1. Repeatedly pick the leftmost unmarked $a$ and mark it (e.g., change it to $X$).
2. Then find the leftmost unmarked $b$ and mark it (change to $Y$).
3. Then find the leftmost unmarked $c$ and mark it (change to $Z$).
4. If at any stage the required symbol is missing, reject.
5. Accept when all $a$, $b$, and $c$ symbols have been marked and no extra symbols remain.

Because each marking pass never needs additional tape beyond what the input already uses (we only overwrite symbols in-place), the tape usage remains linear in the input length.

We will describe an explicit LBA strategy below.

Why this LBA decides $L$

Correctness (sketch):

• If the input is of the form $a^n b^n c^n$:

  • Each iteration consumes exactly one $a$, one $b$, and one $c$ by marking them.
  • After $n$ iterations, all $a$, $b$, and $c$ are marked.
  • The final verification passes, so the LBA accepts.

• If the input is not in $L$:

  • If there are more $a$’s than $b$’s or more $b$’s than $c$’s, then at some iteration one of the required “next unmarked symbol” types will not exist, and the LBA rejects.
  • If the input has symbols out of order (e.g., $b$ before finishing all $a$), the initial structural scan rejects.
  • If there are extra symbols after a region (e.g., leftover $a$’s after $b$’s begin), the structural scan or final verification rejects.

So the machine accepts exactly the strings with equal counts of $a$, $b$, and $c$ and in that specific order.

Tape-length restriction: how we ensure $O(n)$ space

Let $n=|w|$. The construction above:

• performs scans left-to-right and right-to-left over the tape region containing the input,
• overwrites each symbol in-place with one of a finite set of marked variants ($X,Y,Z$),
• never introduces new unbounded work storage like writing long counters on fresh blank cells.

Therefore, the machine’s active region never needs to extend beyond a constant-factor multiple of the original input segment. Since $n$ bounds the number of input cells, and we only use at most those cells for marking and scanning, the space used is:

$\text{space used} = O(n).$

Hence the machine is an LBA by definition.

Visualizing the marking cycle