An Intuitive Procedure for Converting PDA to CFG, by Construction of Single State PDA

2014/11/04 by Arjun Bhardwaj, Bhardwaj, Arjun, N. S. Narayanaswamy +1
Computer Science · #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #cs.FL

paper · pdf · doi:10.48550/arxiv.1411.0813

arxiv created 2014/11/04 · arxiv updated 2014/11/05

Abstract

We present here the proof for an alternative procedure to convert a Push Down Automata (PDA) into a Context Free Grammar (CFG). The procedure involves intermediate conversion to a single state PDA. In view of the authors, this conversion is conceptually intuitive and can serve as a teaching aid for the relevant topics.

Related

• Parikh Image of Pushdown Automata
• Algorithms for Weighted Pushdown Automata
• Convergence and Diversity in the Control Hierarchy
• Deciding semantic finiteness of pushdown processes and first-order grammars w.r.t. bisimulation equivalence
• Visual Execution and Validation of Finite-State Machines and Pushdown Automata