In this section, we look at the (quite remarkable) result that context-free grammars and non-deterministic pushdown automata are equivalent in terms of expressive power. That is, the set of languages which can be generated by context-free grammars is exactly the same as the set of languages which can be recognized by non-deterministic pushdown automata. The reason why I think this result is quite remarkable is because of how different CFGs and PDAs look like on the surface. We will see, however, that there exsits conversion algorithms from both CFGs to PDA and vice-versa.

Converting context-free grammars to pushdown automata

In this first subsection, I will discuss the conversion of CFGs to equivalent PDA. Since I gave a guest lecture on just this topic in Comp 330 during the Fall 2025 semester, I am bookmarking the important sections of that recording below.

• Reminder of CFGs and of PDA : 2:46
• Statement of the theorem of equivalence: 28:05
• CFG-to-PDA algorithm with a running example: 37:42

Conveting pushdown automata to context-free grammars

Unfortunately, I ran out of time in the guest lecture above before I could get to the PDA-to-CFG conversion algorithm. Here are the handwritten notes I was planning on using for that part.