# Why is it undecidable to check the emptiness and finiteness of a context-sensitive grammar?

Context-sensitive languages have context-sensitive grammars, and context-free languages have context-free grammars. Using context-free grammars, we can decide the finiteness and emptiness of context-free languages. Why can't we decide these properties of context-sensitive languages in the same manner, using context-sensitive grammars?

I want to understand the intuition rather than the details.

• (Fuzzy as my memories are, a "sub-question": have another look at the proofs of above claims about CFGs - can you reproduce one of them for CSGs?) Oct 16 '21 at 10:18
• @greybeard I want to understand intuition. Not details. Oct 16 '21 at 11:16
• Oct 16 '21 at 11:56
• @yuval if I write my own answer, could you correct that if I do anything wrong. Oct 16 '21 at 16:24

Here is the idea in a nutshell:

• Given a Turing machine $$M$$, we can construct a context-free grammar $$G$$ such that if $$M$$ halts then $$\overline{L(G)} = \{t\}$$, where $$t$$ is the transcript of the halting computation of $$M$$, and if $$M$$ doesn't halt then $$\overline{L(G)} = \emptyset$$.
Consequently, given a context-free grammar $$G$$, determining whether $$L(G) = \Sigma^*$$ is undecidable.

• Given a Turing machine $$M$$, we can construct a context-sensitive grammar $$G$$ such that if $$M$$ halts then $$L(G) = \{t\}$$, where $$t$$ is the transcript of the halting computation of $$M$$, and $$L(G) = \emptyset$$ otherwise.
Consequently, given a context-sensitive grammar $$G$$, determining whether $$L(G) =\emptyset$$ or whether $$L(G)$$ is finite are both undecidable.

(A transcript is the sequence of configurations describing the execution of the machine, and a configuration consists of the tape contents, the head location, and the state.)

The context-free grammar in the first bullet generates "illegal" transcripts. This requires nondeterminism, and indeed, determining whether $$L(G) = \Sigma^*$$ for a deterministic context-free grammar (i.e., a context-free grammar corresponding to a deterministic pushdown automaton) is decidable.

The context-sensitive grammar in the second bullet is easiest to describe via the equivalent computation model of linear bounded automata: it is easy to construct a linear bounded automaton for the given language. This time the construction requires no nondeterminism, and so determining whether $$L(G) = \emptyset$$ or whether $$L(G)$$ is finite is undecidable even for "deterministic context-sensitive grammars", i.e., the subclass of context-sensitive grammars corresponding to deterministic linear bounded automata.

• Comments are not for extended discussion; this conversation has been moved to chat.
– D.W.
Oct 18 '21 at 15:15