# How to understand pushdown automata intuitively?

What is an intuitive way of understanding what a push down automaton is capable of computing?

Let's start with a finite automaton. Such a device can be viewed as a machine that has a fixed, finite number of boolean variables, like $s =$ "we've seen an even number of $0$'s in the input so far", or $s_i =$ "the input so far, when interpreted as a binary number, is congruent to $i\pmod 3$". Using such a machine, we can count, but only up to a fixed, finite value.
A PDA can be viewed as a FA with one other variable, a stack. With such a machine, we can count up to an arbitrary number. This means that while the language $$L=\{a^nb^n\mid n\ge 0\}$$ can't be accepted by any FA, it can be recognized by a PDA: for each $a$ we see in the input, we push a marker on the stack and for each $b$ we pop a marker off the stack. When we've seen all the input we stop and accept if the stack is empty and reject if it's not.
In a similar way, we can use the stack to store patterns in our input, which is why the palindrome language $$P=\{wcw^R\mid w\in \{a,b\}^*\}$$ can similarly be recognized by a PDA: we push the characters seen on the stack until we see a $c$ and then match the rest of the inputs against the contents of the stack. Since the stack will contain the characters in $w$, we can match the reverse, $w^R$ part of the input against the contents of the stack.