Pushdown Automata

Think of a Pushdown Automata (PDA) as an FSA + a stack. The stack stores extra information - it is the "memory" added to the FSA. In an FSA, the next state depended only on the current state and whether the input bit was a zero or a one. In a PDA, the next state will depend on the current state and the input bit AND the value of the bit on the top of the stack. Also, in addition to 'moving' to the next state, we can also update the stack by either POPPing the top item off the stack or PUSHing the current input bit onto the stack.

Each arrow on the PDA has a 3 part value on it instead of just the input bit (like in an FSA.) The first part is the input bit (exactly the same as the FSA.) The second part is the value of the bit on the top of the stack. Instead of an ACCEPT state, we accept if the stack is empty, when we finish reading the string. If we ever try to POP an empty stack, we crash, meaning that the string is not in the language (rejected.)

 

Nondeterminism does help in PDAs

The main thing to remember is that non-deterministic FSAs and deterministic FSAs are equivlalent. Non-deterministic PDAs are more powerful than deterministic ones; that is, you can recognize a broader class of languages with a nondeterministic PDA.