Pushdown automata can recognize language generated by_________.

Key idea: A pushdown automaton (PDA) recognizes exactly the class of context-free languages.

• PDAs handle nonregular context-free languages by using the stack to track nested or balanced structures (for example, the language of strings of the form a^n b^n).

• Every regular language is also context-free, so a PDA can recognize regular languages too. A PDA can simulate a finite automaton by not using the stack or by using it in a trivial way.

Conclusion: Pushdown automata recognize languages generated by context-free grammars; because regular grammars generate languages that are a subset of context-free languages, pushdown automata also recognize those regular languages.