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

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.

• Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat?
– Raphael
Oct 17, 2016 at 9:54
• The general question for proof techniques has been answered here. Duplicate?
– Raphael
Oct 17, 2016 at 9:56