Linear Bounded Automata: Tape Limits, a Worked LBA Trace and Exam Traps

A linear bounded automaton looks like a Turing machine, so it is easy to assume that “linear bounded” limits the number of transitions. It does not. The limit is on tape space, while the machine may make repeated sweeps across that space. Here is the precise model, its place between a PDA and an unrestricted Turing machine, and a complete trace that decides whether aabbcc belongs to L = {a^k b^k c^k | k >= 1} without leaving the input region.

What a linear bounded automaton actually bounds

A linear bounded automaton, or LBA, is a Turing-machine model whose usable tape is at most c*m cells for input length m. The constant c is independent of the input.

In the end-marker model used here, c=1. The fixed markers cannot be overwritten or crossed, and only the input cells are writable. For aabbcc, k=2, m=6, and positions 1 through 6 form the complete work region. The machine may revisit them and write X, Y, and Z. Bounded does not mean read-only, finite-state, or limited to six steps.

A rule such as delta(q,a)=(p,X,R) still reads, rewrites, changes state, and moves the head. Only a move left from position 1 or right from position 6 is disallowed. Review the Turing Machines worked guide if those mechanics are unfamiliar.

Where an LBA sits in the machine and language hierarchy

An LBA can preserve one marker for each matched a, b, and c inside the input. A single-stack PDA cannot in general enforce all three counts. The CFG and PDA guide explains that lower boundary.

Nondeterministic LBAs characterise context-sensitive languages, equivalently those generated by context-sensitive or noncontracting grammars, subject to the usual empty-string convention. This gives no unbounded workspace and does not make every non-context-free language context-sensitive.

Turn equal-count checking into a bounded marking algorithm

Fix L = {a^k b^k c^k | k >= 1} with tape alphabet a,b,c,X,Y,Z plus fixed end markers. First verify the shape a+ b+ c+ in one left-to-right pass. Reject an empty block or any return to an earlier block, such as an a after a b.

Each matching cycle then does this:

1. Return left, skip X symbols, and replace the leftmost unmarked a with X.

2. Pass remaining a and existing Y symbols, then replace the leftmost unmarked b with Y; reject if none exists.

3. Pass remaining b and existing Z symbols, then replace the leftmost unmarked c with Z; reject if none exists.

4. Return to the left end and repeat.

When no unmarked a remains, accept only if a final sweep finds the form X+Y+Z+. After r cycles, exactly r symbols per block are marked and no cell outside the original m cells has been used.

Worked LBA trace for aabbcc

The format pass accepts the shape aa bb cc. Now preserve all six tape cells through every marking checkpoint:

1. Start: left-end a a b b c c right-end.

2. Cycle 1, mark the first a: left-end X a b b c c right-end.

3. Match its b: left-end X a Y b c c right-end.

4. Match its c: left-end X a Y b Z c right-end.

That completes cycle 1 with one X, one Y, and one Z. The head returns left, skips the first X, and begins the second cycle:

1. Mark the second a: left-end X X Y b Z c right-end.

2. Match the second b: left-end X X Y Y Z c right-end.

3. Match the second c: left-end X X Y Y Z Z right-end.

The next search finds no unmarked a. A final left-to-right sweep also finds no unmarked b or c, so the machine accepts.

The numbers reconcile exactly. k=2 means two a symbols, two b symbols, and two c symbols. Therefore m=3k=3*2=6. The machine used exactly six work cells, and its final counts are #X=#Y=#Z=2. The six symbol changes rewrite the six original cells; the additional checkpoint is the read-only final sweep. Repeated sweeps can take more than linear time even though the occupied space never exceeds m=6 cells.

Rejected inputs show why all three checks are necessary

For aabcc, the symbol counts are #a=2, #b=1, and #c=2. Cycle 1 changes the tape from left-end a a b c c right-end to left-end X a Y Z c right-end. Cycle 2 marks the remaining a, producing left-end X X Y Z c right-end, but finds no unmarked b before the c region, so it rejects.

For aabbc, cycle 1 produces left-end X a Y b Z right-end. Cycle 2 reaches left-end X X Y Y Z right-end, then fails to find an unmarked c before the right end. It also rejects.

The input abacbc fails earlier. During the initial a+ b+ c+ format pass, an a appears after the first b. Equal totals alone are insufficient. The symbols must occur in block order, and all three block counts must be equal.

Why a linear tape bound still gives a decidable class

A fixed-length work region produces only finitely many complete configurations for each input. Suppose this machine has 8 relevant control states, m=6 head positions, and 6 writable symbols in {a,b,c,X,Y,Z}. The tape has 6^6=46,656 possible contents, so there are at most 8*6*6^6 = 2,239,488 configurations. Many are unreachable, so this is an upper bound, not a trace length.

For a deterministic LBA, revisiting the same complete configuration forces the same future and exposes a loop. For a nondeterministic LBA, membership can be decided by searching the finite configuration graph for a path to an accepting configuration. That finite per-input graph is why context-sensitive languages are decidable.

An unrestricted machine can keep expanding its tape, so the same finite-graph argument does not apply. The Turing Machines and Decidability guide develops that contrast. Linear space still does not mean linear time.

How objective questions test LBAs

Common questions ask you to identify a machine from its memory restriction, classify {a^k b^k c^k}, find its work region, continue a marker trace, or test a hierarchy statement. If c=2 and m=12, the allowance is at most c*m=2*12=24 tape cells, not 12 states or 2^12 cells.

Repair these common traps:

• “Linear bounded means linear time” becomes “only space is O(m).”

• “The tape cannot be rewritten” becomes “cells may change inside the boundary.”

• “Every LBA is deterministic” becomes “the standard context-sensitive-language characterisation uses nondeterministic LBAs.”

• “Deterministic and nondeterministic LBAs are known equivalent” becomes “that equality is not known in general.”

• “Every run must obviously halt” becomes “use the finite configuration graph to decide whether an accepting configuration is reachable.”

KnowledgeGate has 5+ published Linear Bounded Automata questions for applying these concepts.

The short version and the next practice step

• An LBA is a tape-bounded Turing machine.

• Its limit is c*m cells, not c*m steps.

• Nondeterministic LBAs characterise context-sensitive languages.

• Marking a, b, and c as X, Y, and Z decides the worked language within the input region.

Now rebuild the aabbcc trace without looking, then explain why aabcc, aabbc, and abacbc fail for three different reasons. Continue with the focused Theory Of Computation / Automata Theory course, use ZERO TO HERO for a broader core-CS route, or browse the CS Fundamentals category subject by subject.