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.

  • $\begingroup$ (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?) $\endgroup$
    – greybeard
    Oct 16 '21 at 10:18
  • $\begingroup$ @greybeard I want to understand intuition. Not details. $\endgroup$
    – Punia
    Oct 16 '21 at 11:16
  • $\begingroup$ Same as cs.stackexchange.com/questions/144815/… $\endgroup$ Oct 16 '21 at 11:56
  • $\begingroup$ @yuval if I write my own answer, could you correct that if I do anything wrong. $\endgroup$
    – Punia
    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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.