A pushdown automaton can recognize {aⁿbⁿ | n ≥ 1} — equal numbers of a's and b's. Why can't a PDA recognize {aⁿbⁿcⁿ | n ≥ 1}, and how does an LBA handle it?
APDAs can recognize {aⁿbⁿcⁿ} — the claim that they cannot is a misconception; both PDAs and LBAs handle this language
BA PDA can count one group against another using its stack, but after matching a's against b's the stack is empty and cannot track the c's; an LBA uses its bounded tape as scratch memory to scan back and forth, counting all three groups
CPDAs fail because they are nondeterministic; a deterministic PDA (DPDA) can handle {aⁿbⁿcⁿ} by using multiple stack symbols
DAn LBA succeeds because it has a larger alphabet, allowing it to mark visited cells with special symbols not available to a PDA
A PDA uses its stack as its only memory beyond the current state. To match aⁿ against bⁿ, the PDA pushes one symbol per 'a', then pops one per 'b'. But when it reaches the c's, the stack is empty — there is nothing left to count with. It cannot check that the number of c's equals n. An LBA has access to its full bounded tape (the entire input), allowing it to scan left and right, mark characters as matched, and count all three groups independently using the tape as scratch memory. The restricted tape is still far more powerful than a stack for this kind of multi-group matching.
Question 2 Multiple Choice
An LBA's tape is bounded to the length of its input. Despite this restriction, the number of distinct configurations an LBA can be in grows with input length n as:
APolynomially in n — bounded tape means bounded configurations
BLinearly in n — proportional to the tape length
CExponentially in n — because each of the n tape cells can hold any of |Γ| symbols, the head can be at n positions, and the machine can be in |Q| states
DDoubly exponentially in n — because each configuration can branch into exponentially many successors
The number of distinct configurations is at most n × |Q| × |Γ|ⁿ, where n is the number of tape cell positions for the head, |Q| is the number of states, and |Γ|ⁿ counts all possible ways the n tape cells can be filled. The |Γ|ⁿ term makes this exponential in n. This is why bounded tape does not mean bounded computation — an LBA has exponentially many configurations and can perform exponential work within its input footprint. This is far more than a PDA (which has polynomial configurations) and explains why LBAs recognize a strictly larger language class.
Question 3 True / False
The question of whether deterministic LBAs recognize all context-sensitive languages — equivalently, whether DLBA = NLBA — remains an open problem in computability theory.
TTrue
FFalse
Answer: True
This is one of the notable open problems in the Chomsky hierarchy. Unlike finite automata (where DFA = NFA) and unlike full Turing machines (where determinism doesn't change the recognizable languages), the relationship between deterministic and nondeterministic LBAs is unresolved. It is known that NLBA recognizes the context-sensitive languages; whether DLBA recognizes exactly the same class is open. This contrasts with pushdown automata, where DPDA ≠ NPDA is proven — deterministic PDAs are strictly weaker.
Question 4 True / False
An LBA recognizes most recursively enumerable languages, since it is a type of Turing machine with primarily a minor restriction on tape usage.
TTrue
FFalse
Answer: False
The tape restriction is not minor — it fundamentally limits computational power. An unrestricted Turing machine can allocate unlimited scratch space, enabling recognition of all recursively enumerable languages including undecidable ones. An LBA is limited to the input's footprint; it cannot generate unbounded tape to store intermediate computations. This restriction carves out exactly the context-sensitive languages — a strict subset of recursively enumerable languages. The containment is proper: there exist recursively enumerable languages (including undecidable ones) that no LBA can recognize.
Question 5 Short Answer
What does the Immerman-Szelepcsényi theorem say about context-sensitive languages, and why is the result non-obvious for nondeterministic machines?
Think about your answer, then reveal below.
Model answer: The theorem proves that the class of context-sensitive languages is closed under complement: if L is context-sensitive, so is its complement. Equivalently, nondeterministic linear space (NSPACE(n)) equals its complement class co-NSPACE(n). This is non-obvious because nondeterminism is asymmetric with respect to acceptance and rejection: a nondeterministic machine accepts a string if some computation path accepts, but proving that no path accepts (i.e., proving the string is not in the language) seems to require a fundamentally different kind of search. The proof circumvents this by using a counting argument — it inductively counts the number of configurations reachable from the initial configuration, allowing a nondeterministic machine to verify non-membership by confirming that no accepting configuration is reachable.
The non-obviousness comes from the asymmetry of nondeterminism. For deterministic machines, the complement is trivial: swap accept and reject states. For nondeterministic machines, this doesn't work — a machine that was supposed to accept on some path now needs to reject on all paths, which requires a fundamentally different argument. Immerman and Szelepcsényi independently discovered that counting reachable configurations provides the needed structure. The result doesn't hold for all nondeterministic space classes (its analogue for NSPACE(log n) gives NL = co-NL), and the question for nondeterministic time classes (NP vs. co-NP) remains open.