1
$\begingroup$

Equality problem is checking if 2 DCFL's or CFL's are producing same language.

I read that it is decidable for DCFL and undecidable for CFL.

If we consider a DCFL like a^n b^2n / n>=1, here we can draw a PDA for this in two ways. So how can we check if 2 DCFL's produce the same language by just looking at the PDA as they are not unique?

$\endgroup$
1
$\begingroup$

We can't. Infinitely many different PDAs for the same DCFL exist.

In 1997, Géraud Sénizergues proved that equivalence of DCFLs is decidable, and he was awarded the Gödel Prize for it.

For general context-free languages, it is undecidable. As a matter of fact, it is already undecidable for linear context-free languages.

$\endgroup$
  • $\begingroup$ And what about CFL ? $\endgroup$ – Zephyr Jul 14 '17 at 14:35
  • $\begingroup$ @Xylene23, I'm not sure what you're trying to ask there, but if you have a follow-up question, please use the 'Ask Question' button to post it as a new question, and provide all the context needed to understand what you're asking. $\endgroup$ – D.W. Jul 14 '17 at 16:24
  • $\begingroup$ The answer was regarding only DCFL and in the question I also asked about NCFL. Also, the answer didn't solve my query about how DCFL's are decidable if they are not unique $\endgroup$ – Zephyr Jul 14 '17 at 16:36
  • $\begingroup$ @Xylene23, I don't see that in the question. The only question I see is "how can we check if 2 DCFL's produce the same language by just looking at the PDA?", and that is already answered. If you have other questions, I suggest you ask a new question about whatever uncertainty you have remaining. The general rule here is one question per post, so if you have two questions, it's often better to post them separately. $\endgroup$ – D.W. Jul 14 '17 at 19:28
  • 1
    $\begingroup$ @Xylene23: 1) it is bad form on this site to ask multiple questions at the same time. 2) If you can't decide something by a given method, that doesn't mean it can't be decided at all. Some other method may exist. In this case, it does. 3) I have added the answer to your second question to my answer. Next time, if you want to save yourself some time and aggravation, go straight to Google or Wikipedia with such questions. $\endgroup$ – reinierpost Jul 15 '17 at 13:41

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.