8
$\begingroup$

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.

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

1 Answer 1

Reset to default
10
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\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.