Proving that the set of grammars generating L or L complement is undecidable

Question

Let $X$ be a regular language, I need to prove that either $\{G \mid L(G) = X\}$ or $\{G \mid L(G) = \overline{X} \}$ is undecidable using the following hint: Use reduction to absurdity supposing that both sets are decidable and concluding that UNIVERSALITY is decidable.

UNIVERSALITY problem is $ \{ G \in CFG \mid L(G) = \Sigma^* \} $, which is known to be undecidable.

I think that the goal is to arrive to the conclusion that UNIVERSALITY is decidable, maybe with a reduction, which means that there is a contradiction in terms of decidabilty of UNIVERSALITY.

Answer 1

Suppose that given a context-free grammar $G$, you could decide whether $L(G) = X$ and whether $L(G) = \overline{X}$. You can use it to decide UNIVERSALITY as follows:

• Create a grammar $G_1$ such that $L(G_1) = L(G) \cap X$.
• Create a grammar $G_2$ such that $L(G_2) = L(G) \cap \overline{X}$.
• Accept if $L(G_1) = X$ and $L(G_2) = \overline{X}$.

The point is that we can construct the grammars $G_1,G_2$ algorithmically.

Note that for some $X$, deciding whether $L(G) = X$ could be decidable. The simplest example is when $X = \emptyset$. A more sophisticated example is $X = w^*$ (this follows from Parikh's theorem, for example).