A pushdown automaton is a way to implement a context-free grammar in a similar way we design DFA for a regular grammar. A DFA can remember a finite amount of information, but a PDA can remember an infinite amount of information.
A stack does two operations −- Push − a new symbol is added at the top.
- Pop − the top symbol is read and removed.
Push − a new symbol is added at the top.
Pop − the top symbol is read and removed.
Pushdown Automata
- A pushdown automaton (PDA) is a finite
automaton equipped with a stack-based memory. - Each transition
- is based on the current input symbol and the top of
the stack, - optionally pops the top of the stack, and
- optionally pushes new symbols onto the stack.
- Initially, the stack holds a special symbol Z0
that
indicates the bottom of the stack.
Our First PDA
- Consider the language
L = { w ∈ Σ* | w is a string of balanced
digits }
over Σ = { 0, 1 } - We can exploit the stack to our advantage:
- Whenever we see a 0, push it onto the stack.
- Whenever we see a 1, pop the corresponding 0
from the stack (or fail if not matched) - When input is consumed, if the stack is empty, accept.
