<p>jflap is pretty nice and can do this. See here: <a href="http://www.cs.duke.edu/csed/jflap/" rel="nofollow">http://www.cs.duke.edu/csed/jflap/</a>.</p>

CC BY-SA 2.5
2010-10-14T08:37:02.303Z
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?
Raphael
CC BY-SA 2.5
2010-10-14T13:54:26.520Z
@Raphael, apparently it does: http://www.cs.duke.edu/csed/jflap/tutorial/pda/cfg/index.html
DaniCL
CC BY-SA 2.5
2010-10-14T03:37:38.883Z
2010-10-14T03:37:38.883Z
Sariel Har-Peled
<p>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). </p>

<p>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.</p>

CC BY-SA 3.0
2013-01-01T23:37:09.213Z
mmm. I would attribute that proof to Chomsky, Evey and Schützenberger.
Hendrik Jan
CC BY-SA 2.5
2010-10-14T02:30:46.320Z
funny. normally one wants the other way around :)
Suresh Venkat
<automata-theory><fl.formal-languages><grammars><software>
Tool for translating PDAs to CFGs
Xodarap
# Tool for translating PDAs to CFGs

(Asked by: username_0 on 2010-10-14)

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.

**Tags:** automata-theory, fl.formal-languages, grammars, software

> **Comments:**
> **username_2**: funny. normally one wants the other way around :)  
> **username_1**: mmm. I would attribute that proof to Chomsky, Evey and Schützenberger.  

---

## 1 answers

### Answer by username_3 on 2010-10-14. Score: 10 | Accepted answer

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

> **Comments:**
> **username_4**: 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?  
> **username_5**: @username_4, apparently it does: http://www.cs.duke.edu/csed/jflap/tutorial/pda/cfg/index.html  

---

