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.

  • $\begingroup$ 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? $\endgroup$
    – Raphael
    Commented Oct 17, 2016 at 9:54
  • $\begingroup$ The general question for proof techniques has been answered here. Duplicate? $\endgroup$
    – Raphael
    Commented Oct 17, 2016 at 9:56

1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.