Foundations — Pumping lemma for regular languages — proof and using to show non-regularity

Before you can read the parent note, you must own every piece of its notation. This page builds each one from absolutely nothing, in an order where each idea leans only on the ones before it.

---

1. The alphabet $\Sigma$ — the box of allowed letters

The picture: a small box holding tiles. For the parent note the box is usually $\Sigma =\{a,b\}$ or $\Sigma =\{0,1\}$.

Why the topic needs it: every string, language, and machine on this page is built out of these tiles. Nothing exists before we fix the box.

---

2. A string $w$ and its length $|w|$ — tiles in a row

The picture: tiles laid in a line. a a b is a string of length $3$, so $|aab|=3$.

The special empty string is written $\epsilon$ (Greek "epsilon"): a row with zero tiles, $|\epsilon |=0$. It is a real, legal string — like an empty hand of tiles.

---

3. Powers of a string: $a^n$ and $y^i$ — shorthand for repetition

The picture: a stamp. $a^n$ = stamp the letter $a$ exactly $n$ times.

Why the topic needs it: the whole lemma is about repeating a middle chunk $y$. Writing $y^i$ is how we say "spin the loop $i$ times". And $y^0=\epsilon$ is exactly "pump the loop down to nothing" — the case beginners forget.

---

4. A language $L$ — the set of "accepted" strings

The picture: a fenced field. Every string is a dot; the ones inside the fence belong to $L$, the ones outside do not. The symbol $w\in L$ ("$w$ is an element of $L$") means the dot $w$ is inside the fence; $w\notin L$ means outside.

Why the topic needs it: "regular or not regular" is a question about a language — about which dots the fence encloses.

---

5. The DFA — a finite machine that walks a graph

This is the heart. The parent note writes $M=(Q,\Sigma ,\delta ,q_0,F)$. Let us unwrap every letter.

The picture (figure above): circles connected by arrows. You start on $q_0$, and for each tile in your string you follow the arrow labelled with that tile. When the tiles run out, look down: standing on a double-ring circle ⇒ accept; otherwise reject.

See Finite Automata (DFA NFA) for the full machine; here we only need "walk the graph, land on a circle."

Why the topic needs it: the DFA is what "regular" is defined by — the crack the pumping lemma pries open is the finiteness of $Q$.

---

6. Acceptance and the language $L(M)$ — linking machine to language

The picture: each string $w$ is fed into the machine; the machine lights up green (accept) or red (reject). $L(M)$ is the collection of all the green ones — exactly the dots inside the fence from Section 4.

Why the topic needs it: this notation is the bridge between a machine (Section 5) and a language (Section 4). Without "$L(M)$" we cannot say precisely what it means for a DFA to "recognise" a language — and that is the very next definition.

---

7. Regular language — defined precisely

The picture: a language $L$ is "regular" if you can draw a finite circles-and-arrows machine whose green set (Section 6) matches $L$ dot-for-dot.

Equivalently, $L$ is regular iff it is described by a regular expression or accepted by an NFA — see Finite Automata (DFA NFA). All three views describe the same class.

Why the topic needs it: the pumping lemma begins with the words "If $L$ is regular …". Everything downstream — the existence of a pumping length, the loop, the contradiction — hangs on this one definition. If you cannot cash out "regular" as "$\exists$ DFA $M$ with $L(M)=L$", the lemma has no starting point.

---

8. The pumping length $p$ — where the number comes from

The picture: count the circles in the machine's graph. That count is $p$.

Why the topic needs it: every later use of $p$ — "the first $p+1$ footprints", "$p$ holes", "$|xy|\le p$" — is really about the number of circles in the DFA. The magic threshold $p$ is not pulled from thin air: it is exactly $|Q|$. That is why a string longer than $p$ is forced to repeat a state.

---

9. The run: the sequence of states $r_0,r_1,\dots ,r_n$

The picture: footprints on the graph, one footprint per tile read (plus the starting one). A string of length $n$ leaves $n+1$ footprints.

Why the topic needs it: the proof watches these footprints. If two footprints land on the same circle, everything between them is a loop — and that loop is the $y$ the lemma pumps.

---

10. The Pigeonhole Principle — why a repeat is forced

The picture (figure above): $p+1$ pigeons trying to fit into $p$ holes — one hole is forced to double up.

In this topic: the pigeons are the first $p+1$ footprints $r_0,\dots ,r_p$; the holes are the $p=|Q|$ circles of the machine. More footprints than circles ⇒ two footprints share a circle ⇒ a repeated state ⇒ a loop exists.

Full treatment: Pigeonhole Principle.

Why the topic needs it: this is the engine of the proof. Without it "the machine must repeat a state" is just a hope; pigeonhole makes it a certainty.

---

11. The split $w=xyz$ — cutting the string at the loop

The picture (figure above): the string is a ribbon in three coloured segments; the middle segment $y$ corresponds to a circular arrow that returns to the same circle. Because $y$ takes you $r_j\to r_j$, you may run it $0,1,2,\dots$ times and always end on $r_j$ before continuing with $z$.

The two size rules that make the split useful:

• $|y|\ge 1$: the loop is non-empty, because $j<k$ means at least one tile is inside it.
• $|xy|\le p$: the repeat was found among the first $p+1$ footprints, so the cut $y$ sits within the first $p$ tiles.

Why the topic needs it: $xyz$ is the entire vocabulary of the pumping lemma. Every proof manipulates these three pieces.

---

12. Subset and logic symbols — the glue

The picture: $\forall$ is a checklist you must pass every row of; $\exists$ is finding one winning row.

Why the topic needs it: the lemma's quantifier order decides who chooses what in the adversary game. Misreading these symbols is the most common way the whole proof goes wrong.

---

13. The Pumping Lemma — the statement these pieces build

Now every symbol is earned, we can write the theorem the parent note proves and uses. Read it slowly, matching each symbol to its section above.

---

Prerequisite map — how the pieces feed the lemma

Read the arrows as "is needed for". Follow the three parallel streams that meet at the lemma:

• Language stream: alphabet → strings → language $L$; and separately, the DFA gives $L(M)$, which defines regular.
• Combinatorics stream: the run's footprints + the pigeonhole principle force a repeated state.
• Structure stream: the repeated state creates the split $w=xyz$; string powers $y^i$ let us spin its loop.

All three streams, plus the logic symbols, converge on the statement of the pumping lemma, which then powers non-regularity proofs.

Related tools you will meet later: Regular Expressions and Finite Automata (DFA NFA) both define regular languages; Myhill–Nerode Theorem is an alternative non-regularity weapon; Closure Properties of Regular Languages often shortens proofs; and the same loop-idea reappears in the Pumping Lemma for Context-Free Languages. This whole page is the runway to the parent: the Pumping Lemma note.

---

Equipment checklist

Try to answer each before revealing. If any stalls you, re-read its section above.