Course contentsShow
← Computer Science
Lesson 1831 of 2,87241. Context-Free LanguagesFree lesson

Acceptance by Final State vs Empty Stack

Two acceptance criteria for PDAs and how they define when a string is accepted by the automaton.

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.