Which is not the correct statement(s)? Choose the option that correctly…

Concept: In the Chomsky hierarchy the language classes form a chain of inclusions — regular ⊂ context-free ⊂ context-sensitive ⊂ recursive (decidable) ⊂ recursively enumerable. A context-sensitive language is exactly what a linear bounded automaton accepts: a Turing machine, in general nondeterministic, whose head never leaves the tape cells that already hold the input. A recursive language is one for which some Turing machine halts on every input and answers membership yes or no.

Application: The two statements are the two separate halves of the relation between those classes, so settle each one on its own.

1. Statement (i). Let M be a linear bounded automaton for a context-sensitive language, with |Q| states and tape alphabet Γ, run on an input of length n. A configuration records the state, the head position and the tape contents, so on that input M has at most |Q| · n · |Γ|n distinct configurations — a finite number.

2. Those configurations form a finite directed graph, with an edge from each configuration to every configuration M can move to from it in one step. Search that graph from the start configuration, marking each configuration as it is visited so that none is ever expanded twice. Marking is what makes the search finite even though M may be nondeterministic: a repeated configuration is simply never re-explored.

3. The search inspects at most |Q| · n · |Γ|n configurations and so always terminates, and it reports yes exactly when some accepting configuration is reachable, which is exactly the condition for M to accept the input. The procedure therefore halts on every input and decides membership, which is the definition of a recursive language, so every context-sensitive language is recursive.

4. Statement (ii). Fix an effective enumeration G1, G2, G3, … of all context-sensitive grammars and w1, w2, w3, … of all strings over the alphabet, then define the diagonal language L = { wi : wi ∉ L(Gi) }.

5. To decide whether wi belongs to L, run the always-halting membership procedure of step 3 on the grammar Gi and the string wi, then invert its answer; L is therefore recursive.

6. For every index i the language L disagrees with L(Gi) on the string wi, so L is generated by no context-sensitive grammar, and a recursive language outside the context-sensitive class exists.

Cross-check: The two statements are the two halves of the single relation context-sensitive ⊊ recursive — (i) supplies the containment and (ii) supplies its strictness — so they reinforce each other instead of competing. The other offered combinations fail on one half or the other:

• “(i) is true, (ii) is false” would make the context-sensitive and recursive classes coincide, which the diagonal language of steps 4–6 rules out.

• “(i) is false, (ii) is false” would place some context-sensitive language outside the decidable languages, which the terminating configuration-graph search of steps 1–3 rules out.

• “(i) is false and (ii) is true” keeps the strict separation but still leaves a context-sensitive language undecidable, so its first half fails for the same reason.

Result: Both (i) and (ii) are true statements, so neither of the two is an incorrect statement, and the choice reading “(i) is true and (ii) is true” is the one that reports them correctly.