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

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.

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).