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$ – Suresh Venkat Oct 14 '10 at 2:30
  • $\begingroup$ mmm. I would attribute that proof to Chomsky, Evey and Schützenberger. $\endgroup$ – Hendrik Jan Jan 1 '13 at 23:37

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

| cite | improve this answer | |
  • $\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 '10 at 8:37
  • $\begingroup$ @Raphael, apparently it does: cs.duke.edu/csed/jflap/tutorial/pda/cfg/index.html $\endgroup$ – DaniCL Oct 14 '10 at 13:54

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.