Final state ↔ empty stack
Hopcroft 2e §6.2.3–6.2.4. A PDA can accept by reaching a final state or by draining its stack, and the two are interconvertible. Both constructions turn on one new stack symbol, pushed underneath everything: going one way it is the tripwire that reveals the original stack just emptied, going the other it is the safety net that stops an accidental acceptance.
Machine (accepts by final state):
Original — L(P)
Converted — N(P′)
Narration
A new start state p0 pushes Z0 above a new bottom marker X0 and hands control to q0. X0 is the safety net: if the original machine drains its own stack without having accepted, X0 is still there and the new machine does not accept by accident.
Both machines on the same strings
The theorem says the languages are equal; here is a sample of it. (A sample is evidence, not the proof — the proof is the construction above.)
| w | original | converted |
|---|---|---|
| aaabbb | accepts | accepts |
| ab | accepts | accepts |
| ε | accepts | accepts |
| aab | rejects | rejects |
| ba | rejects | rejects |