# Transform PDA with acceptance of final state + empty stack to just final state

"It is a well known result that every PDA with acceptance condition of an empty stack and reachability of a final state can be transformed to an equivalent PDA with acceptance condition requiring only reachability of a final state. Transform PDA ____ to an equivalent PDA with acceptance requiring only reachability of a final state."

I'm just a bit confused on what steps I have do to. My thought process is...final state + empty stack acceptance is a subset of just a final state acceptance? When I try to 'transform' my PDA, it ends up looking exactly the same as the original.

## 1 Answer

Given a PDA $M$, you can define the following associated languages:

• The language of all words $w$ such that there is a computation path for the PDA on $w$ in which it ends at a final state with an empty stack. We denote this language by $L_1(M)$.

• The language of all words $w$ such that there is a computation path for the PDA on $w$ in which it ends at a final state. We denote this language by $L_2(M)$.

The two languages are not always the same, that is, it could well be that $L_1(M) \neq L_2(M)$. You have to show that for each PDA $M$ there is another PDA $M'$ such that $L_1(M) = L_2(M')$.

• How do I do that? That sounds like induction to me. However, I have to transform a PDA by empty + final acceptance to just a PDA with final state acceptence. So say I have a PDA which represents language a^nb^n. How would I be able to show this as just a final state acceptance, rather than final state + empty stack? – Jake Mar 21 '17 at 1:55
• Induction is not a good idea in this case. You will use it perhaps to prove the equivalence of the two machines, but not to construct $M'$ from $M$. – Yuval Filmus Mar 21 '17 at 8:35