Undecidability of checking whether all words can be generated from a context-free grammar?

Question

I know it's undecidable, but how to prove it?

Let me explain the problem clearer. The problem is not to check whether some given word can be generated, but whether ALL words are possible to generate in this CFG.

Answer 1

Let $T$ be a one-tape Turing machine. A snapshot of a Turing machine is the contents of its tape, where the location of the head is preceded by the current state of the machine (encoded using a disjoint set of symbols).

We can encode a halting computation of $T$ on the empty string as a string $s_0 \# s_1^R s_2 \# s_3^R \# \ldots \# s_n$ (or $s_n^R$, according to the parity of $n$), where $s_0,\ldots,s_n$ is the sequence of snapshots encountered during the run of $T$.

We can check that a string does not code a halting computation as follows:

• It is of the form $\Sigma^*\# s \# \Sigma^*$, where $s$ doesn't contain $\#$ but doesn't correspond to a valid snapshot. (More accurately, we have two corner cases corresponding to the first and last snapshot, and we might have to count the number of $\#$ in the prefix to determine whether it should be a snapshot or its reverse.)
• It is of the form $s_0 \# \Sigma^*$, where $s_0$ doesn't contain $\#$ but doesn't correspond to an initial snapshot.
• It is of the form $\Sigma^* \# s_n$ (or $s_n^R$), where $s_n$ doesn't contain $\#$ but doesn't correspond to a final snapshot (i.e., the Turing machine is not in a final state).
• It is of the form $\Sigma^* \# s_i \# s_{i+1}^R \# \Sigma^*$ (or $s_i^R \# s_{i+1}$, according to the parity of $\#$ in the prefix), where $s_i,s_{i+1}$ do not contain $\#$ but $s_{i+1}$ is not the snapshot following $s_i$.

With some care, we can express all of these conditions as a context-free grammar. Here it is important that we encode the computation by reversing any other snapshot, since this enables us to ascertain that $s_{i+1}$ doesn't follow $s_i$ in a context-free manner (roughly speaking, this is just the language $w\#w^R$ with small modifications).

This context-free grammar generates $\Sigma^*$ if and only if $T$ doesn't halt on the empty string. It follows that universality of context-free grammars is co-r.e.-hard. It is also co-r.e.: if the context-free grammar is not universal, then there is a witness for it, namely a string not generated by the grammar (recall that the word problem for context-free grammars is decidable). Hence universality of context-free grammars is co-r.e.-complete.