Proof that PDA's with different definitions have same expressive power

Question

Let $P$ be a push down automaton $(Q,\Sigma,\Gamma,\delta,q_s,F)$, where

• $Q$ is the set of states,
• $\Sigma$ is the input alphabet
• $\Gamma$ is the stack alphabet
• $\delta$ is the transition function with signature $Q\times(\Sigma\cup\{\epsilon\})\times(\Gamma\cup\{\epsilon\})\to\mathcal{P}(Q\times(\Gamma\cup\{\epsilon\}))$
• $q_s$ is the initial state
• $F$ is the set of acceptable states.

We suppose that at every transition at 1 symbol of the input string is read, 1 symbol of the stack is popped, 1 symbol is pushed and we can change our state. A general (informal) definition of the acceptance of a string is: we accept the string when we end in an acceptable state with an empty string (whatever the stack contains).

However, there are other possible definitions of the acceptance of a string by $P$. Some possibilities:

• The string is accepted when both the string and stack are empty (even when the current state would not be an acceptable state).
• The string is accepted when both the string and stack are empty and we are in an acceptable state.

One could also change the definition of the PDA as follows:

• One can push more than 1 symbol to the stack in 1 transition.

My question is, how can 1 (both formally and informally) proof that the power of the PDA does not change by using another definition? Alternatively, one could say that the languages determined by the different PDA's are the same.

Answer 1

You prove it the same way you prove that any two models of computation are equivalent: you show that, for every machine of type A, the language accepted by that machine is accepted by some machine of type B, and vice-versa. Sometimes, this is trivial, for example if A is just a restricted version of B (e.g., proving that every language accepted by a DFA is accepted by an NFA). In other cases, it involves simulating the features or acceptance criteria of A using B (e.g., proving that every language accepted by an NFA is accepted by a DFA by using the subset construction).

If you're looking for details of how to prove all the equivalences mentioned in your question, then I think your question is too broad. You should be able to find some of them in any good textbook that covers PDAs, and you'll probably find the rest as exercises because the specific proofs probably use the same general principles.