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


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.