Sabemos que todos os autômatos push-down são representáveis usando gramáticas sem contexto. Além disso, existe um algoritmo para construir um CFG a partir de qualquer PDA (por exemplo, a prova de Sipser na introdução à teoria da computação).
Existem ferramentas que fazem essa tradução? Ou seja, eu posso colocar um conjunto de funções de transição e ele retornará um CFG equivalente.
Respostas:
O jflap é muito bom e pode fazer isso. Veja aqui: http://www.cs.duke.edu/csed/jflap/ .
fonte