For which computational model is it currently UNKNOWN whether the deterministic and nondeterministic versions recognize the same class of languages?
AFinite automata — every NFA can be converted to an equivalent DFA via subset construction
BTuring machines — a deterministic TM can simulate any nondeterministic TM
CLinear bounded automata — whether DLBA = NLBA has not been resolved
DPushdown automata — deterministic and nondeterministic PDAs are already proven equivalent
For finite automata, DFA = NFA is proven via subset construction. For Turing machines, DTM = NTM is proven by exhaustive simulation (with exponential slowdown). For pushdown automata, DPDA ≠ NPDA — deterministic PDAs recognize a strict subset of context-free languages. For LBAs, the question is genuinely open: we do not know whether DLBA = NLBA. This is the LBA problem, connected to the complexity question of whether DSPACE(n) = NSPACE(n). The techniques that resolve the question for other models all fail for LBAs due to space constraints.
Question 2 Multiple Choice
A linear bounded automaton is given input string w of length n. Which statement correctly describes what the LBA can do during computation?
AIt can read the input but cannot write to the tape — the LBA is read-only within the input region
BIt can read, write, and move in both directions, but only within the O(n) tape cells corresponding to the input, bounded by endmarkers
CIt can access any tape cell but must halt within O(n) steps to qualify as linear-bounded
DIt can move only rightward within the input to bound memory use; leftward movement would allow revisiting cells
An LBA has full Turing machine capabilities within its bounded region: it can read, write, and move in both directions freely. The constraint is purely spatial — the head cannot move beyond the O(n) cells delimited by the input's endmarkers. The 'linear bounded' refers to tape space, not time. The LBA is not read-only and is not restricted to unidirectional movement. This space restriction is what gives the LBA its intermediate position: less powerful than an unrestricted TM but more powerful than a pushdown automaton.
Question 3 True / False
An LBA is guaranteed to halt on every input, unlike a general Turing machine which may loop forever.
TTrue
FFalse
Answer: True
An LBA operates on a tape of size O(n). Because both the tape cells (finite, bounded by n) and the state set (finite) are finite, the total number of distinct LBA configurations is finite. If the LBA ever revisits an identical configuration (same state, same tape contents, same head position), it is in a detectable infinite loop. Since there are only finitely many configurations, any computation that hasn't halted within that count must be looping. This guaranteed termination makes the membership problem for context-sensitive languages decidable — unlike the undecidable membership problem for recursively enumerable languages.
Question 4 True / False
The language {ww | w ∈ {a,b}*} — strings consisting of a word followed by its exact copy — is context-free and can be recognized by a nondeterministic pushdown automaton.
TTrue
FFalse
Answer: False
The language {ww} is NOT context-free. The pumping lemma for context-free languages shows it cannot be recognized by any pushdown automaton. It IS context-sensitive and can be recognized by a linear bounded automaton: the LBA uses its tape to compare the first half of the string with the second half, requiring memory proportional to n/2 — within the O(n) bound. This is a canonical example illustrating why LBAs are strictly more expressive than PDAs. The superficially similar language {ww^R} (w followed by its reverse) IS context-free — the difference being that a stack can handle reversal but not copying.
Question 5 Short Answer
What makes the LBA problem — whether DLBA = NLBA — fundamentally harder to resolve than the analogous question for finite automata or Turing machines?
Think about your answer, then reveal below.
Model answer: For finite automata, DFA = NFA is proven by subset construction: track all NFA states simultaneously in a single DFA state. But applying this to LBAs would require the DLBA to track exponentially many possible NLBA configurations simultaneously, violating the O(n) space bound. For Turing machines, DTM = NTM is proven by exhaustive simulation of all nondeterministic branches, but this also requires superlinear space and time — again violating the linear space constraint. No known technique converts an NLBA to a DLBA within the linear space bound, yet no proof exists that it is impossible.
The LBA problem is equivalent to the complexity-theoretic question: DSPACE(n) = NSPACE(n)? This remains open. It sits in an awkward middle ground: the techniques that work for simpler models break the space bound, and the arguments that resolve questions about TMs do not apply to bounded-memory machines. This makes the LBA problem one of the longest-standing open problems in formal language theory — not because it seems fundamentally hard (unlike P vs. NP, which most believe is resolved by separation) but because available proof techniques are too weak to settle it either way.