PHD Discussions Logo

Ask, Learn and Accelerate in your PhD Research

Question Icon Post Your Answer

Question Icon

How can recursive automata be shown to accept the same languages as pushdown automata?

I'm delving into the hierarchy of formal machines and have hit a conceptual wall. While I understand both automata types independently, I need clarity on the constructive proof strategy. How does one formally map the recursive call-return mechanism to a stack's push-pop behavior?

All Answers (1 Answers In All)

By Sourabh Answered 1 year ago

Having taught this equivalence, the key is to see the stack as explicitly encoding the execution stack of recursive calls. I would recommend starting by defining a recursive automaton's configuration to include its "call depth." The core of the proof is a constructive simulation: each recursive call becomes a push of the return state and local variables onto the PDA's stack. A return corresponds to a pop, restoring context. I have seen students grasp it best by building a simple PDA that simulates a recursive automaton for a specific language, like balanced parentheses, which makes the state-stack mapping concrete.

Your Answer