Acceptance by Final State vs Empty Stack
You'll learn the two standard ways a pushdown automaton decides whether to accept an input string.
A pushdown automaton (PDA) processes input symbols while manipulating a stack, but when does it actually accept a string? There are two distinct acceptance criteria, and they define different—but equally powerful—ways of recognizing context-free languages.
Acceptance by Final State
Under this criterion, a PDA accepts a string if, after reading all input symbols, the automaton ends in one of its designated final (accepting) states. The stack contents at that moment don't matter—it could be empty, full, or anything in between. You simply check: "Am I in a state marked as accepting?"
Think of it like finishing a maze: you accept the path if you end up at the exit, regardless of what you're carrying in your backpack.
Acceptance by Empty Stack
Here, a PDA accepts a string if, after consuming all input, the stack becomes empty. The current state doesn't matter—only that you've successfully cleared the stack. This criterion treats the stack as a "to-do list": acceptance means you've processed everything and have nothing left.
Imagine balancing parentheses: you push opening brackets and pop matching closing ones. If the stack is empty at the end, the string is balanced.
Why Two Criteria?
Both methods are equally powerful—any language accepted by final state can be accepted by empty stack, and vice versa. You can convert between them algorithmically. The choice often depends on which is more natural for the language you're modeling. Balanced parentheses? Empty stack is intuitive. Pattern matching with explicit end markers? Final state might be clearer.
Key Takeaway: PDAs can accept strings either by reaching a designated final state or by emptying the stack; both criteria are equivalent in expressive power but offer different conceptual approaches to recognition.