In this section, we will be discussing pushdown automata (PDA), which are the automata equivalent (in expressive power) to context-free grammars. PDA are similar in nature to NFA+$\varepsilon$ except that they are equipped with an additional data structure: a stack. I will first give some general intuitions about how PDA work. The rest of the section will be examples and exercises about creating PDA which recognize context-free languages. Note that, technically speaking, this is a presention of NPDA: non-deterministic pushdown automata. Deterministic pushdown automta are not covered in this section.

What are pushdown automata?

In this video, I present the high-level intuitions of PDA. This video is taken from a recording of a lecture that I gave in Fall 2024.

Designing a PDA that recognizes a language

In this this video, I present the more “nitty-gritty” details of PDA by describing how to design one that accepts the (infamously non-regular) language $\{a^nb^n : n \geq 0\}$. Note that in this video I am assuming that the bottom-of-the-stack marker is the dollar sign, i.e. $, and that it has already been placed at the stack’s bottom.

Exercises

Exercise. Design a PDA which recognizes the language $\{ww^R : w \in \{a,b\}^*\}$.

Exercise. Design a PDA which recognizes the language $L = \{w : w \in \{a,b\}^*, n_a(w) = n_b(w)\}$.

Exercise. Design a PDA which recognizes the language $L = \{a^{2n}b^{3n} : n \geq 0 \}$.

Exercise. Design a PDA which recognizes the language $L = \{a^nb^{2n} : n \geq 0 \} \cup \{a^mb^n : m \geq n \geq 0\}$.