is a PDA. We can define a new PDA N so that L(M) L(N) and N is guaranteed to have an empty stack at the end of any accepting computation. Informally, the construction is as follows: Add three new states q,g,d, and one new stack symbol #. One of the new states qh will be the new start state and it has a spontaneous transition to the old start state qo which pushes the new stack symbol # to the stack. The transitions between the old states are all the same. From each of the old accept states, add a spontaneous transition (that doesn't modify the stack) to the second new state qa . In this state 2, pop all old stack symbols from the stack without reading any input. When the new stack symbol # is on the top of the stack, transition to the third new state ds and accept. Complete the formalization of this description by giving the full formal definition of N