We know that all push down automata are representable using context-free grammars. Furthermore, there is an algorithm to construct a CFG from any PDA (e.g. Sipser's proof in intro to theory of computation).

Are there any tools which do this translation? I.e. I can put in a set of transition functions and it will return an equivalent CFG.

  • 1
    $\begingroup$ funny. normally one wants the other way around :) $\endgroup$ Oct 14, 2010 at 2:30
  • $\begingroup$ mmm. I would attribute that proof to Chomsky, Evey and Schützenberger. $\endgroup$ Jan 1, 2013 at 23:37

1 Answer 1


jflap is pretty nice and can do this. See here: http://www.cs.duke.edu/csed/jflap/.

  • $\begingroup$ Does is implement the usual construction that is used for proving equivalence of PDA and CFG (we called it "triple construction") or does it do something else? $\endgroup$
    – Raphael
    Oct 14, 2010 at 8:37
  • $\begingroup$ @Raphael, apparently it does: cs.duke.edu/csed/jflap/tutorial/pda/cfg/index.html $\endgroup$
    – DaniCL
    Oct 14, 2010 at 13:54

Your Answer

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

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