1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Isn't that decidable? Remove $\epsilon$ productions, and then you get a CFG that will cause any derivation to include words of non-decreasing length. Then search the possible derivations up-to the given length. Are you perhaps thinking of other kinds of grammars? Am I missing something? $\endgroup$ – chi May 12 at 19:39
  • 1
    $\begingroup$ The problem is not to check whether some given word can be generated from a CFG, but rather whether ALL words can be. $\endgroup$ – InferionEmperor May 12 at 20:04
  • $\begingroup$ Do not put "edit" sections after your original question, in general. Instead, modify the question so that it reads the way you think it should for the first-time readers. $\endgroup$ – Apass.Jack May 12 at 20:34
  • $\begingroup$ Ok, sorry for this, I haven't read all the rules yet. $\endgroup$ – InferionEmperor May 12 at 20:47
  • $\begingroup$ @InferionEmperor No problem, I was just helping to make the post looks better. $\endgroup$ – Apass.Jack May 12 at 23:28
1
$\begingroup$

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.

$\endgroup$

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.