# Decidability of whether CFL = RL

Let L1 be a language generated by a CFG. Let L2 be a language generated by a regular grammar. Is L1 = L2 ?

Is the above problem decidable or undecidable ?

If L1 = L2 then L1 $\cap$ L2' = $\phi$

So the above problem can be written as

CFL $\cap$ RL = $\phi$ or CFL = $\phi$ which is decidable.

So the answer should be decidable according to me but my professor marked it wrong saying it's undecidable

Where am I going wrong ?

• Note that CFL is typically used to denote the class of all context-free languages. That makes your post confusing. – Raphael Dec 5 '17 at 12:22

If $L_1 = L_2$ then $L_1 \cap \overline{L_2} = \emptyset$
While that is true, the reverse is false. The right-hand side is also true if $L_2 \supsetneq L_2$. Therefore, deciding the right-hand side does not solve equality.
• Can we check (L1 $\cap$ L2') $\cup$ (L1' $\cap$ L2) = $\phi$ to solve the question? – Zephyr Dec 5 '17 at 12:33