0
$\begingroup$

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 ?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Note that CFL is typically used to denote the class of all context-free languages. That makes your post confusing. $\endgroup$ – Raphael♦ Dec 5 '17 at 12:22
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Can we check (L1 $\cap$ L2') $\cup$ (L1' $\cap$ L2) = $\phi$ to solve the question? $\endgroup$ – Zephyr Dec 5 '17 at 12:33
  • 1
    $\begingroup$ @Zephyr For basic set theory, I suggest you freshen up your basics, e.g. using the Book of Proof. For follow-up computability questions, please post a new question. (You may want try and prove your professor's claim first.) $\endgroup$ – Raphael♦ Dec 5 '17 at 12:39

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.