Pushdown automata are a type of automaton that use a stack to recognize context-free languages. They are more powerful than finite-state machines but less powerful than Turing machines. Nested stack automata allow full access and can recognize a larger set of languages than pushdown automata.

A foundational course that introduces formal languages, automata, computability, and complexity theories, including finite automata, Turing machines, and P/NP classes.