Pushdown Automata
FA vs. PDA
FA vs. PDA
These automata are like nondeterministic finite automata but have
an extra component called a stack. The stack provides additional
memory beyond the finite amount available in the control. The stack
allows pushdown automata to recognize some nonregular
languages.
Pushdown Automata
• A pushdown automaton (PDA) can write symbols on the stack and
read them back later. Writing a symbol “pushes down” all the other
symbols on the stack.
• At any time the symbol on the top of the stack can be read and
removed. The remaining symbols then move back up.
• Writing a symbol on the stack is often referred to as pushing the
symbol, and removing a symbol is referred to as popping it. Note that
all access to the stack, for both reading and writing, may be done only
at the top.
Pushdown Automata
• A stack is valuable because it can hold an unlimited amount of
information.
• Recall that a finite automaton is unable to recognize the language
{0n1n | n ≥ 0} because it cannot store very large numbers in its finite
memory.
• A PDA is able to recognize this language because it can use its stack to
store the number of 0s it has seen.
• Thus the unlimited nature of a stack allows the PDA to store numbers
of unbounded size.
How a PDA recognizes {0 1
n n | n ≥ 0}
• Read symbols from the input.
• As each 0 is read, push it onto the stack.
• As soon as 1s are seen, pop a 0 off the stack for each 1 read.
• If reading the input is finished exactly when the stack becomes empty
of 0s, accept the input.
• If the stack becomes empty while 1s remain or if the 1s are finished
while the stack still contains 0s or if any 0s appear in the input
following 1s, reject the input.
Deterministic vs. Nondeterminitic PDAs
• Pushdown automata may be nondeterministic.
• Deterministic and nondeterministic pushdown automata are not
equivalent in power.
Example
State Diagram
Testing Empty Stack
Example
Example