Foundations — Equivalence of CFGs and PDAs

This page is the ground floor. The parent topic throws a lot of notation at you: $V$, $\Sigma$, $R$, $S$, $\delta$, $\Gamma$, $Z_0$, $A_{pq}$, ${\Rightarrow }^{\ast }$, $\epsilon$. We define each one from zero, anchor it to a picture, and say why the topic needs it — in an order where every item leans only on the ones before it.

1. Symbols, strings, and the empty string

Why the topic needs $\epsilon$. In Direction 1 the PDA applies a grammar rule without reading any input — that "read nothing" is written $\epsilon$. In Direction 2 the rule $A_{pp}\to \epsilon$ means "go nowhere, read nothing." If you don't have a name for "the string of length zero," you cannot write either.

2. Sets and the star $\ast$

Picture ${\Sigma }^{\ast }$ as an ever-growing list: first $\epsilon$, then all length-1 strings, then all length-2 strings, forever.

Why the topic needs $\ast$. A grammar rule $A\to \alpha$ says $\alpha$ is some string of variables-and-terminals; that "some string, any length" is precisely what $\ast$ captures.

3. The last-in-first-out picture: a stack

Everything in this topic rides on one data structure. Meet it before any automaton.

Why the topic needs it. In Direction 1 the stack literally stores "the part of the string I still owe you." In Direction 2, a balanced push-then-pop on the stack is the bracket structure that a grammar variable expands into.

4. A grammar: $G=(V,\Sigma ,R,S)$

Now we can read the parent's grammar tuple, piece by piece.

5. Derivation arrows: $\Rightarrow$ and ${\Rightarrow }^{\ast }$

Picture a chain of pictures: $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aabb$. Each arrow is one box being replaced.

Why the topic needs ${\Rightarrow }^{\ast }$. The variable $A_{pq}$ in Direction 2 is defined by $A_{pq}{\Rightarrow }^{\ast }w$ — "$A_{pq}$ can be rewritten, in some number of steps, into the pure string $w$." No star arrow, no way to state that meaning.

6. A machine's control: $Q$, $q_0$, $F$, and $\delta$

The parent writes moves like $\delta (q,\epsilon ,A)\ni (q,\alpha )$. Decode it: in state $q$, reading nothing ($\epsilon$), with $A$ on top of the stack, one allowed outcome ($\ni$ means "contains as a member") is: stay in $q$ and push $\alpha$.

7. The stack alphabet: $\Gamma$ and $Z_0$

Why two alphabets? The machine reads input letters ($\Sigma$) but may want to remember them using different scratch symbols ($\Gamma$). Keeping them separate lets the stack store bookkeeping (like grammar variables) that never appears in the input.

8. Putting a PDA together: $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,Z_0,F)$

9. The triple variable $A_{pq}$

You now have every piece to read Direction 2's key invention.

Why the topic needs it. This is the bridge that turns "a run of the machine" into "an expansion of a grammar box." Because a balanced dip is a nesting shape (§3), it is exactly what a CFG variable can generate — that is the entire trick of Direction 2.

How these foundations feed the topic

Read top to bottom: raw symbols build strings; strings and the star give both grammars and the stack picture; the stack + states make a PDA; grammars + arrows give derivations; and the balanced-run variable $A_{pq}$ fuses machine-runs with grammar-boxes, delivering the equivalence in the parent topic.

Equipment checklist

Cover the right side and answer each before moving on.