Is is decidable whether 2 given PDAs accept the same language?

Also, is it decidable whether the language accepted by a given grammar is context free (the given grammar could be unrestricted but there may exist an equivalent CFG for it)

  • $\begingroup$ Equality of context-free languages is undecidable, in fact, it is already undecidable for linear context-free languages (in which the derivation always contains just a single nonterminal). See cs.stackexchange.com/q/57377 $\endgroup$ – Hendrik Jan Apr 23 '17 at 14:32
  • 1
    $\begingroup$ Please restrict yourself to only one question per post. $\endgroup$ – Raphael Apr 23 '17 at 15:36
  • $\begingroup$ We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered. $\endgroup$ – Raphael Apr 23 '17 at 15:36
  • $\begingroup$ Also, both questions have been answered on Computer Science before. I suggest you do some searching. $\endgroup$ – Raphael Apr 23 '17 at 15:37
  • $\begingroup$ Your first question is answered in the obvious place on Wikipedia: en.wikipedia.org/wiki/Context-free_language#Decidability. We expect you to do a significant amount of research before asking (including checking standard resources, like textbooks or Wikipedia), and to show us in the question what research you've done. If your question is answered in the obvious place on Wikipedia, it would probably benefit you to do more research before asking in the future, as there's little point in us repeating material available in standard resources. $\endgroup$ – D.W. Apr 23 '17 at 17:16

These problems are undecidable. For more other problems, visit this page https://www.cs.wcupa.edu/rkline/fcs/grammar-undecidable.html

  • $\begingroup$ Link-only answers are not worth a lot. If that links break (and it probably will), the content of your answer is almost nil. $\endgroup$ – Raphael Apr 23 '17 at 15:37

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.