Consider a language $L_1$ that is recursively enumerate, $L_2$ that is regular, and $L_3$ that is context-free.

Are the following problems algorithmically decidable?

  1. Is $L_1 \cap L_2 = L_3$?
  2. Is $L_1 \cap L_3 = L_2$?

I think problem 1 is undecidable since $L_1 \cap L_2$ is a recursively enumerable language it can be expressed as a Turing machine and since $L_3$ is context free it can be expressed as a Grammar or Turing machine. Since we cannot determine the equivalence of two Turing machines, the problem is undecidable.

I think problem 2 is also undecidable for similar reasons, only the right hand side ($L_2$) is regular instead of context-free.

Am I correct?

  • 1
    $\begingroup$ Yes, you are. Basically, (1) is reducible from the universality problem for CFG, and (2) is reducible from the universality problem for TM. However, note that questions of the type "verify my answer" are discouraged on this site. $\endgroup$ – Shaull Aug 13 at 19:07
  • 1
    $\begingroup$ Can you share the context or situation where you encountered this question? I notice we've had three questions recently that were about the same exercise: cs.stackexchange.com/q/129242/755, cs.stackexchange.com/q/129231/755, cs.stackexchange.com/q/129254/755. $\endgroup$ – D.W. Aug 14 at 3:39

Both questions are undecidable. Notice that the empty language is both regular and context-free. Thus we can state that the problem of determining if $L_1 \cap L_2$ is context-free is at least as hard as determining if $L_1$ is context-free (and similarly determining if $L_1 \cap L_3$ is a regular language is at least as hard as determining if $L_1$ is a regular language). By Rice's Theorem any non-trivial property about a Turing-Machine is undecidable and thus your two questions are undecidable.

For a detailed proof/answer to your second question look at this post. IT shows how you would apply Rice's Theorem in your cases.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy