Skip to content
Tutorials Center
My learning

Topics

Lesson 30 of 59 Β· Context-Sensitive and Other Models

Linear Bounded Automata

A linear bounded automaton is a Turing machine whose tape is limited to the input. Learn how LBAs match context-sensitive languages and detect infinite loops.

A linear bounded automaton (LBA) is a Turing machine that is not allowed to use more tape than the input occupies. The input is written between two end markers < and >; the head can read and rewrite cells, move left and right, but it can never move past the markers, and it can never overwrite them. So the amount of memory is linear in the input length, hence the name.

LBAs are the machine model for the context-sensitive languages: a language is context-sensitive if and only if some (nondeterministic) LBA accepts it. This matches the grammar side, where sentential forms never grow longer than the word being derived.

Definition

An LBA is a Turing machine (Q, Ξ£, Ξ“, Ξ΄, q0, <, >, F) with:

  • a tape alphabet Ξ“ βŠ‡ Ξ£ that includes extra marking symbols;
  • end markers < and > placed around the input, which may never be erased or moved over;
  • the usual transitions Ξ΄(q, X) = (p, Y, D) with D ∈ {L, R}.

Because the tape is bounded, the machine has memory of about n Β· log|Ξ“| bits plus its state. The trick that makes LBAs more powerful than PDAs is that the head can move back and forth over the same cells and use markers like X, Y, Z to keep track of progress, where a PDA can only touch the top of its stack.

flowchart LR
    A["tape: a a b b c c<br/>between two end markers"] --> B["head moves left and right<br/>inside the markers"]
    B --> C["cells can be marked<br/>X, Y, Z"]
    C --> D["accept, reject<br/>or repeat a configuration"]

The memory never grows beyond the input, so the number of distinct configurations is finite.

Counting configurations

A configuration is the state, the head position and the whole tape content. For an input of length n there are at most

|Q| Β· (n + 2) Β· |Ξ“|^n

configurations. That is a huge number, but it is finite. If a computation runs for more steps than this bound, some configuration has repeated, and since the machine is deterministic, it will cycle forever. This gives an algorithm that always halts: simulate the LBA, remember all configurations seen, and declare "reject" if one repeats.

Theorem. The acceptance problem for LBAs (does LBA M accept w?) is decidable.

Contrast this with ordinary Turing machines, where the same question is undecidable (see the halting problem). Bounded memory is the difference.

An LBA for a^n b^n c^n

The recognizer marks one a (as X), one b (as Y) and one c (as Z) in every round, sweeping back to the left each time. It accepts when everything is marked and nothing is left over. The machine below works on the tape < w >.

TEXT
qs,<   -> q0,<,R          start: step over the left marker
q0,a   -> q1,X,R          mark an a
q1,a   -> q1,a,R   q1,Y -> q1,Y,R
q1,b   -> q2,Y,R          mark a b
q2,b   -> q2,b,R   q2,Z -> q2,Z,R
q2,c   -> q3,Z,L          mark a c, then go back
q3,a/b/Y/Z -> q3,.,L      sweep left until the X
q3,X   -> q0,X,R          start the next round
q0,Y   -> q4,Y,R          no a's left: check that nothing else is left
q4,Y/Z -> q4,.,R
q4,>   -> qa,>,S          reached the right marker: accept

The program below stores the rules in a table and runs the LBA with loop detection. It tests all strings over {a, b, c} up to length 8 against the true definition.

Python An LBA for a^n b^n c^n with loop detection

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The configuration bound printed at the end (with the rough numbers 8 states and 8 tape symbols) is about 16.8 million, huge but finite. The simulation never needs anywhere near that many steps in practice.

A machine that loops forever

An ordinary Turing machine can run forever without anyone being able to tell in advance. An LBA cannot hide an infinite run: it must repeat a configuration. The program below bounces between the end markers forever and gets caught at once.

Python Catching an infinite loop

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The number of steps before detection grows with the input length, but the verdict always comes.

What LBAs can and cannot decide

Question about an LBA M Decidable?
Does M accept input w? Yes (finite configurations), but PSPACE-complete
Does M halt on w? Yes (accept, reject or repeat)
Is L(M) empty? No
Is L(M) all strings? No
Are L(M1) and L(M2) equal? No

Emptiness is undecidable because an LBA can verify a computation history of an arbitrary Turing machine: the history is a long string, and the LBA checks that consecutive configurations follow the machine's rules. A history exists exactly when the Turing machine accepts, so deciding emptiness would solve the halting problem.

An important open question from the 1960s, the LBA problem, asked whether deterministic LBAs are as powerful as nondeterministic ones, equivalently whether DLBA = NLBA. It is still unsolved. Closure under complement for nondeterministic LBAs was settled in 1987 (Immerman and SzelepcsΓ©nyi).

Check your understanding

Quick check Β· 4 questions

of 4 answered You scored / 4 Β· perfect!

  1. 1. What restriction defines a linear bounded automaton?

    An LBA is a Turing machine whose head can never leave the input region delimited by the end markers.
  2. 2. Which languages are accepted by LBAs?

    LBAs and context-sensitive grammars define the same class of languages.
  3. 3. Why can we always decide whether an LBA accepts an input w?

    A finite configuration space means an infinite run must revisit a configuration, which we can detect.
  4. 4. Which problem is undecidable for LBAs?

    Emptiness is undecidable: an LBA can check computation histories of arbitrary Turing machines.

Summary

  • An LBA is a Turing machine restricted to the tape cells holding its input (plus end markers).
  • LBAs recognize exactly the context-sensitive languages.
  • The number of configurations is finite, so acceptance and halting are decidable.
  • A simple marking strategy (X, Y, Z) recognizes a^n b^n c^n.
  • Emptiness and equivalence for LBAs are undecidable; whether DLBA = NLBA is open.

Next: Counter and multi-stack machines