Foundations — Pushdown automata (PDA) — configuration, acceptance by empty stack - final state

Before you can read a single line of the parent note, you must own every symbol it throws at you. Below, each symbol is built from nothing: plain words → the picture → why the topic can't live without it. Read top to bottom; each rung needs the one below it.

0. The rock-bottom pieces: alphabets, symbols, strings

Picture it: think of a paper ticket tape. Each little cell holds one symbol; reading left to right gives you the string.

WHY two alphabets? The letters you read and the tokens you store serve different jobs. On the input you might see a, but on the stack you might store a bookkeeping token A. Keeping $\Sigma$ and $\Gamma$ separate lets the machine invent its own private memory symbols.

WHY $\epsilon$ exists at all: the machine sometimes wants to move without reading a letter (rearrange plates), or accept a string that has no letters left. Both need a name for "nothing." That name is $\epsilon$.

1. The star operator ${\Sigma }^{\ast }$ and ${\Gamma }^{\ast }$

Picture it: $X^{\ast }$ is an infinite bag of tickets — the blank ticket $\epsilon$, all length-1 tickets, all length-2 tickets, and so on forever. Each individual ticket is finite; the bag is infinite.

WHY the topic needs it: the parent writes a configuration as living in $Q\times {\Sigma }^{\ast }\times {\Gamma }^{\ast }$. The "remaining input" is some string over $\Sigma$ (an element of ${\Sigma }^{\ast }$), and the "stack contents" is some string over $\Gamma$ (an element of ${\Gamma }^{\ast }$). The star is how we say "any finite sequence, we don't fix the length."

2. Sets, membership $\in$, subset $\subseteq$, power set $\mathcal{P}$

Picture it: a set is a fenced field of objects. $\in$ is "this cow stands inside the fence." $\subseteq$ is "this small pen sits entirely inside the big field." $\mathcal{P}(S)$ is "the catalogue of every possible pen you could draw inside $S$."

WHY the topic needs each one:

• $F\subseteq Q$ says the final states are some of the states.
• $q_0\in Q$ says the start state is one particular state.
• $\delta$'s output is a member of ${\mathcal{P}}_{\text{finite}}(\dots )$ — i.e. a finite set of possible moves, which is exactly how nondeterminism ("try several branches") is written down.

3. Ordered pairs, triples, and the product $\times$

Picture it: a grid. Put $A$ along the bottom edge, $B$ up the side; every cell of the grid is one pair $(a,b)$. $A\times B$ is "all the cells."

WHY the topic needs it: a configuration is a triple $(q,w,\gamma )$ — one state, one leftover input, one stack. Saying it lives in $Q\times {\Sigma }^{\ast }\times {\Gamma }^{\ast }$ is the precise way to say "pick one item from each of these three sets, in this order." Tuples are how the machine's entire momentary situation gets packaged into a single object.

4. What a "state" and the finite control are

Picture it: a dial with a fixed number of labelled positions. The dial can click from one position to another, but there are only so many positions — you cannot store "I've seen 4000 letters" on a dial with 3 positions.

WHY the topic needs it (the whole punchline): the finite control alone is a finite automaton, which cannot count without bound. Bolt on a stack and suddenly it can. Understanding "the state is bounded memory" is why the stack matters. If you have met the finite-control idea before, it is exactly the machinery of a nondeterministic finite automaton (NFA).

5. The stack — LIFO memory

Picture it: a spring-loaded plate dispenser in a canteen. You can only ever add or take the top plate. The plate at the bottom is untouchable until everything above it is gone.

WHY: without a marker, the machine cannot tell "stack is nearly empty" from "stack has real work left." $Z_0$ is a floor tile you can see so you know when you've reached the bottom.

6. The transition function $\delta$ and the arrow $\to$

WHY this exact shape: at any instant the machine can look at only three things — its mood, the one letter under the read head, and the one plate on top. So the input to $\delta$ is a triple of exactly those. The output is a set (because nondeterminism allows several legal moves) of pairs (because a move both changes the mood and rewrites the top of the stack).

7. The configuration triple and the yields arrows $⊢$, ${⊢}^{\ast }$

Picture it: freeze the machine mid-run and photograph three things — the dial position, the still-unread part of the tape, and the plate pile (drawn on its side, top plate at the left). That photo is the configuration. Crucially it holds everything about the future and nothing about the past.

Picture it: $⊢$ is one frame-to-next-frame step of a film. ${⊢}^{\ast }$ is "you can get from this frame to that frame by playing some number of frames, possibly zero."

WHY both: a single rule of $\delta$ produces a single $⊢$ step; but "the machine accepts $w$" is a statement about a whole run, i.e. many steps chained — that is what ${⊢}^{\ast }$ names in one symbol.

8. Acceptance — two finish lines

WHY name two: they are different finish lines but, provably, they let a PDA recognise exactly the same class of languages — the context-free languages. The parent note builds both and converts between them; here you just need to know they are two answers to "when did the machine pass?"

Prerequisite map

Equipment checklist

Self-test: cover the right side and answer each aloud.