0

I am working on a project that requires me to compare two PDA to check whether they accept the same language or not. I have converted these PDAs into their corresponding context free languages, but I have no idea how to proceed further.

1 Answer 1

0

For CFL the problem of equality is undecidable - you can show by reduction of the problem of universality of CFL to the HALT problem (the general one defined over Turing Machines), and the language equality is pretty much only narrowed down universality.

I'm not sure what kind of project are you working on, but consider using DCFL, if it's a "practical" problem, and if it's academic problem/homework, you should do the reduct I mentioned higher.

EDIT: I did not considered that you might just want to compare two specific languanges as a one-time thing. Unfortunately there is no way to generalize answer, as the problem might still be undecidable.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.