Questions: Context-Sensitive Languages and Type 1 Grammars

Question 1

Which of the following languages is context-sensitive but NOT context-free?

• A. {aⁿbⁿ | n ≥ 1} — equal numbers of a's followed by b's
• B. {aⁿbⁿcⁿ | n ≥ 1} — equal numbers of a's, b's, and c's in sequence
• C. {a*b*} — any number of a's followed by any number of b's
• D. All regular languages, since regular ⊂ context-free ⊂ context-sensitive

Answer: (B)

{aⁿbⁿ} is context-free — it is the classic example generated by S → aSb | ab and accepted by a pushdown automaton. {a*b*} is regular. Regular languages are indeed nested inside context-sensitive, but that makes them context-sensitive too, not examples that are CSL but not CFL. {aⁿbⁿcⁿ} is the canonical example that is NOT context-free (proven via the pumping lemma — no pushdown automaton can track three linked counters) but IS context-sensitive: a context-sensitive grammar can coordinate all three regions using context-aware productions.

Question 2

What machine model corresponds exactly to context-sensitive languages?

• A. A deterministic pushdown automaton (with a single stack)
• B. An unrestricted nondeterministic Turing machine with unbounded tape
• C. A nondeterministic linear-bounded automaton (tape bounded linearly by input length)
• D. A nondeterministic pushdown automaton with two stacks

Answer: (C)

The linear-bounded automaton (LBA) is a nondeterministic Turing machine whose tape is restricted to at most a constant multiple of the input length. This tape bound is exactly the resource needed to handle the coordination problems (like counting three linked regions) that defeat pushdown automata, while remaining strictly less powerful than an unrestricted TM with unbounded tape. The Chomsky correspondence: regular ↔ DFA, context-free ↔ PDA, context-sensitive ↔ LBA, recursively enumerable ↔ unrestricted TM.

Question 3

Every context-free language is also a context-sensitive language.

• T. True
• F. False

Answer: True

The Chomsky hierarchy is a strict nesting: regular ⊂ context-free ⊂ context-sensitive ⊂ recursively enumerable. Every CFL is a special case of a CSL — any context-free grammar can be viewed as a context-sensitive grammar where the context strings α and β in productions αAβ → αγβ happen to always be empty. The 'strictly contains' relationship means there exist CSLs that are not CFLs (like {aⁿbⁿcⁿ}), but every CFL qualifies as a CSL.

Question 4

A context-sensitive grammar allows productions where the replacement string γ can be shorter than the nonterminal A being replaced, as long as the surrounding context strings are non-empty.

• T. True
• F. False

Answer: False

This is precisely wrong. The defining constraint of context-sensitive (Type 1) grammars is that γ must be NON-EMPTY — strings can never shrink during a derivation. The production form αAβ → αγβ with |γ| ≥ 1 ensures string length is non-decreasing. This non-shrinking property is what distinguishes Type 1 from Type 0 (unrestricted) grammars, where γ can be empty (allowing strings to shrink), and is what bounds the tape needed to simulate the grammar to a linear function of the input length.

Question 5

What is the key syntactic constraint that makes a grammar 'context-sensitive' rather than 'unrestricted,' and why does it determine the computational power of the corresponding machine model?

Model answer: The constraint is that the replacement string γ must be non-empty in every production αAβ → αγβ — derivations are non-shrinking. This means the length of any sentential form during derivation never exceeds the length of the final string. Because the string never shrinks, the nondeterministic Turing machine simulating the grammar only ever needs tape proportional to the current string length, which is bounded by the input length times a constant. This is exactly the tape bound of a linear-bounded automaton. An unrestricted grammar allows γ to be empty (erasure rules), so strings can grow and then shrink, requiring potentially unbounded tape and corresponding to the full power of an unrestricted Turing machine.

The non-shrinking constraint is a resource bound in disguise: it limits the working space the machine needs to verify membership, placing context-sensitive languages precisely at the level of linear-space computation in the complexity landscape.