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

The three conditions are:

1. $|y|\ge 1$ — the pumpable middle is non-empty.
2. $|xy|\le p$ — the middle lives inside the first $p$ symbols.
3. $x{y}^{i}z\in L$ for every $i\ge 0$.

The adversary (the lemma) chooses the split; you only choose $w$ and $i$.

Number the symbols $\mathrm{1..5}$: $a_1{a}_2{b}_3{b}_4{b}_5$. Condition $|xy|\le p=3$ means $y$ must finish by position $3$. Condition $|y|\ge 1$ means $y$ is non-empty. So $y$ is a non-empty substring lying entirely within positions $1,2,3$. The legal $y$'s are: $a_1$, $a_2$, $b_3$, $a_1{a}_2$, $a_2{b}_3$, $a_1{a}_2{b}_3$. That is $6$ possible middles.

False. The lemma is necessary, not sufficient: every regular language pumps, but some non-regular languages also pump (see Example 4 in the parent note). To prove regularity you build a DFA/regex or use Myhill–Nerode Theorem.

1. Assume $L$ regular $\Rightarrow$ pumping length $p$ exists.
2. Choose $w=a^p{b}^p$. Then $w\in L$ and $|w|=2p\ge p$. ✓
3. Adversary splits $w=xyz$ with $|y|\ge 1$, $|xy|\le p$. The first $p$ symbols are all $a$'s, so $x$ and $y$ lie entirely inside the $a$-block: $y=a^m$ with $1\le m\le p$.
4. Pump $i=2$: $x{y}^{2}z=a^{p+m}{b}^p$.
5. Since $m\ge 1$, $p+m\ne p$, so $a^{p+m}{b}^p\notin L$. This contradicts condition 3. $\Rightarrow L$ is not regular. $■$

1. Assume regular $\Rightarrow p$.
2. Choose $w=a^p{b}^{p+1}\in L$, $|w|=2p+1\ge p$. ✓
3. $|xy|\le p$ traps $y$ inside the $a$-block: $y=a^m$, $1\le m\le p$.
4. Pump $i=2$: $x{y}^{2}z=a^{p+m}{b}^{p+1}$. This has $p+m$ $a$'s and $p+1$ $b$'s.
5. Membership requires the $b$-count to be exactly one more than the $a$-count: $(p+1)=(p+m)+1$, which simplifies to $m=0$ — impossible since $m\ge 1$. So $x{y}^{2}z\notin L$. Contradiction $\Rightarrow$ not regular. $■$

1. Assume regular $\Rightarrow p$.
2. Choose $w=0^p{1}^{2p}\in L$, $|w|=3p\ge p$. ✓
3. First $p$ symbols are all $0$'s, so $y=0^m$, $1\le m\le p$.
4. Pump $i=2$: $x{y}^{2}z=0^{p+m}{1}^{2p}$.
5. Membership needs the $1$-count to be double the $0$-count: $2p=2(p+m)=2p+2m$, forcing $m=0$ — impossible. So $x{y}^{2}z\notin L$. Contradiction $\Rightarrow$ not regular. $■$

Flaw: the student chose the split $y=a^3$. But the split is chosen by the adversary, not by you — you cannot assume $y$ is any particular thing. Repair: derive constraints on $y$ from the conditions instead. From $|xy|\le p$ and the first $p$ symbols being $a$'s, the only thing you may conclude is $y=a^m$ for some $1\le m\le p$. Then pumping $i=2$ gives $a^{p+m}{b}^p\notin L$ for every such $m$. That handles all splits at once — which is exactly what the proof requires.

Choose $w=a^{p+1}{b}^p\in L$ (since $p+1>p$), $|w|=2p+1\ge p$. ✓ The $a$-block occupies the first $p+1$ symbols, and $|xy|\le p$ traps $y=a^m$, $1\le m\le p$.

Why $i=2$ fails: $x{y}^{2}z=a^{p+1+m}{b}^p$. Here $p+1+m>p$ is still true, so the string is still in $L$ — no contradiction. Pumping up only widens the gap, keeping membership.

Why $i=0$ works: $x{y}^{0}z=a^{p+1-m}{b}^p$. Choosing $i=0$ removes $a$'s, shrinking the gap. If $m\ge 1$ and specifically when the removal makes $a$-count $\le b$-count, membership breaks. The worst case for us is $m=1$, giving $a^p{b}^p$, where $p>p$ is false, so $a^p{b}^p\notin L$. For any $m\ge 1$, $p+1-m\le p$, so the string is not in $L$. Contradiction $\Rightarrow$ not regular. $■$

Moral: choose the direction of pumping that moves toward the boundary of membership.

1. Assume regular $\Rightarrow p$.
2. Choose $w=a^{p^2}\in L$; $|w|=p^2\ge p$. ✓
3. Any split gives $y=a^m$ with $1\le m=|y|\le |xy|\le p$.
4. Pump $i=2$: length becomes $p^2+m$.
5. Key inequality: the gap between consecutive squares at $p^2$ is $(p+1{)}^2-p^2=2p+1.$ Since $m\le p<2p+1$, we get $p^2<p^2+m<p^2+2p+1=(p+1{)}^2$. So $p^2+m$ sits strictly between two consecutive perfect squares — it cannot itself be a perfect square. Hence $a^{p^2+m}\notin L$. Contradiction $\Rightarrow$ not regular. $■$

Look at the figure above: the pale-yellow mark $p^2+m$ lands in the shaded "no-square zone" between $p^2$ and $(p+1{)}^2$; the yellow arrow shows the gap $2p+1$ is wider than the biggest jump $m$ pumping can make, so no square is reachable.

1. Assume regular $\Rightarrow p$.
2. Choose $w_0=0^{p}10^{p}1$. This is $ww$ with $w=0^{p}1$, so $w_0\in L$; $|w_0|=2p+2\ge p$. ✓
3. The first $p$ symbols are all $0$'s, so $|xy|\le p$ forces $y=0^m$, $1\le m\le p$, drawn from the first zero-block.
4. Pump $i=2$: $x{y}^{2}z=0^{p+m}10^{p}1$.
5. For this to be of the form $uu$, split it into two equal halves. The total length is $2p+2+m$; if $m$ is odd the length is odd and cannot be $uu$ at all. If $m$ is even, the first half is $0^{p+m}1\dots$ but the string has only one $1$ before the middle on the left and the tail structure $\dots 0^{p}1$ on the right cannot match — concretely the first half would contain more than $p$ zeros before its first $1$, while the second half has exactly $p$ zeros before its $1$, so the two halves differ. Either way $x{y}^{2}z\notin L$. Contradiction $\Rightarrow$ not regular. $■$ (A cleaner alternative: choosing $w_0=0^{p}10^{p}1$ and $i=0$ gives $0^{p-m}10^{p}1$, whose two halves $0^{p-m}1$ and $0^{p}1$ differ since $m\ge 1$.)

The goal is to transport non-regularity from a known hard case into $L$, using only closure properties (no pumping of $L$).

Known fact (our anchor): $L_3=\{a^n{b}^n{c}^n:n\ge 0\}$ is not regular. (Standard pumping proof: choose $a^p{b}^p{c}^p$, $|xy|\le p$ traps $y=a^m$, pump up to break the $a$-count.)

Suppose, for contradiction, $L=\{a^n{b}^n\}$ were regular.

Step 1 — define an intermediate language. Let $L^{\prime \prime }=L\cdot c^{\ast }=\{a^n{b}^n{c}^k:n\ge 0,k\ge 0\}.$ Here $c^{\ast }$ (all strings of $c$'s) is regular, and regular languages are closed under concatenation. So if $L$ were regular, $L^{\prime \prime }$ would be regular too.

Step 2 — intersect with a regular filter. The set $R=\{a^n{b}^n:n\ge 0\}$ is what we assumed regular; instead of re-using it, take the plain regular set of "matching $b$–$c$ tails." Concretely, note that $L_3=L^{\prime \prime }\cap R_{bc},R_{bc}=\{a^i{b}^j{c}^j:i,j\ge 0\}?$ — but $R_{bc}$ is itself non-regular, so that filter is illegal. The clean fix: filter $L^{\prime \prime }$ so that the $c$-count is forced to equal the $b$-count using regularity of $L$ again. Precisely, apply the symmetric construction: let $L^{\prime \prime \prime }=a^{\ast }\cdot \{b^n{c}^n:n\ge 0\}.$ If $\{b^n{c}^n\}$ were regular then $L^{\prime \prime \prime }$ would be regular (concatenation with the regular set $a^{\ast }$). Now both filters are (assumed) regular, and $L_3=\{a^n{b}^n{c}^n\}=L^{\prime \prime }\cap L^{\prime \prime \prime }.$

Why this intersection equals $L_3$ (step by step). A string $s$ lies in $L^{\prime \prime }\cap L^{\prime \prime \prime }$ iff it satisfies both memberships:

• $s\in L^{\prime \prime }=\{a^n{b}^n{c}^k\}$ forces $s=a^n{b}^n{c}^k$: an $a$-block, then an equal-length $b$-block, then some $c$'s.
• $s\in L^{\prime \prime \prime }=\{a^i{b}^m{c}^m\}$ forces $s=a^i{b}^m{c}^m$: some $a$'s, then a $b$-block equal in length to the $c$-block. Matching the two forms symbol-block by symbol-block: the shape must be $a^{\bullet }{b}^{\bullet }{c}^{\bullet }$, with $\#a=\#b$ (from $L^{\prime \prime }$) and $\#b=\#c$ (from $L^{\prime \prime \prime }$). Together $\#a=\#b=\#c$, i.e. $s=a^n{b}^n{c}^n$. So $L^{\prime \prime }\cap L^{\prime \prime \prime }=L_3$.

Step 3 — closure contradiction. Regular languages are closed under intersection. So if $L=\{a^n{b}^n\}$ and $\{b^n{c}^n\}$ were both regular, then $L^{\prime \prime }$ and $L^{\prime \prime \prime }$ would be regular, hence $L_3=L^{\prime \prime }\cap L^{\prime \prime \prime }$ would be regular. But $L_3$ is not regular — contradiction. Therefore at least one of $L=\{a^n{b}^n\}$, $\{b^n{c}^n\}$ is non-regular; by the left–right symmetry of the argument the same reasoning proves each individually non-regular, so $L=\{a^n{b}^n\}$ is not regular. $■$

Point of the exercise: closure under concatenation and intersection lets you build $L_3$ out of the assumed-regular pieces, then the known non-regularity of $L_3$ back-propagates to refute the assumption — no pumping of $L$ needed.

It passes. Let $p=1$ be the claimed pumping length. Take any $w\in L$, $|w|\ge 1$.

Split with $x=\epsilon$ and $y=$ the first symbol of $w$, $z=$ the rest. Then $|y|=1\ge 1$ and $|xy|=1\le p=1$. We check $x{y}^{i}z\in L$ for all $i\ge 0$:

• If $w$ starts with $a$ and has $\ge 2$ $a$'s (i.e. $i_a\ge 2$): pumping the leading $a$ keeps $i_a\ge 2$, so the antecedent $i=1$ is false, making the implication vacuously true — the string stays in $L$.
• If $w$ starts with $a$ and has exactly one $a$ (so $j=k$ must hold): pumping that single $a$ up gives $\ge 2$ $a$'s (antecedent false ⇒ in $L$), and pumping down ($i=0$) gives $0$ $a$'s (antecedent false ⇒ in $L$).
• If $w$ starts with $b$ or $c$: then $i_a=0\ne 1$, antecedent false, and pumping the first $b$ (or $c$) still leaves $i_a=0\ne 1$; string stays in $L$.

In every case some legal split pumps forever inside $L$, so $L$ satisfies the pumping lemma.

But $L$ is not regular. Restrict via intersection with the regular set $a{b}^{\ast }{c}^{\ast }$ (closure under intersection): $L\cap a{b}^{\ast }{c}^{\ast }=\{a{b}^j{c}^j:j\ge 0\}$, which is essentially $\{b^n{c}^n\}$ shifted — provably non-regular by pumping. Since regular languages are closed under intersection with regular sets, $L$ cannot be regular. $■$

Correct tool: use closure properties or Myhill–Nerode Theorem — the pumping lemma alone is powerless here.

Myhill–Nerode idea: if $L$ is regular, the number of classes under the relation $x\equiv y⟺(\text{for all suffixes }z:xz\in L\iff yz\in L)$ is finite (it equals the number of states of the minimal DFA). To prove non-regularity, exhibit infinitely many strings that are pairwise distinguishable — meaning for each pair there is a suffix $z$ that one can complete into $L$ but the other cannot.

Construct the infinite family. Take $S=\{a^0,a^1,a^2,a^3,\dots \}=\{a^k:k\ge 0\},$ an infinite set of strings.

Show every pair is distinguishable. Pick any two distinct members $a^i$ and $a^j$ with $i\ne j$. Use the suffix $z=b^i$:

• $a^{i}z=a^i{b}^i\in L$ (equal counts). ✓
• $a^{j}z=a^j{b}^i\notin L$ (since $j\ne i$, the counts differ). ✗

So the suffix $z=b^i$ distinguishes $a^i$ from $a^j$: appended to one it lands in $L$, appended to the other it does not. Because this works for every pair $i\ne j$, all the strings $a^0,a^1,a^2,\dots$ lie in pairwise distinct equivalence classes.

Finish the argument. We have exhibited infinitely many mutually distinguishable strings, so the relation $\equiv$ has infinitely many classes. But a regular language has only finitely many. Contradiction $\Rightarrow L=\{a^n{b}^n\}$ is not regular. $■$

Compare: where pumping needed a clever $w$ and case analysis over splits, Myhill–Nerode just needs an infinite distinguishable family — often cleaner, and it is an if-and-only-if characterisation (unlike pumping).

Naive pumping of $a^p{b}^{p+1}$ fails: the adversary picks $y=a^m$, and pumping up gives $a^{p+m}{b}^{p+1}$, which is in $L$ as long as $p+m\ne p+1$ — the adversary can arrange this to stay inside $L$. We need a sharper string.

Choose $w=a^p{b}^{p+p!}$, where $p!=1\cdot 2\cdots p$. This is in $L$ (since $p\ne p+p!$ as $p!\ge 1$) and $|w|=2p+p!\ge p$. ✓

The adversary splits with $y=a^m$, $1\le m\le p$. Now pump to $i=1+\frac{p!}{m}$. Why is this an integer? Because $m\le p$, so $m$ divides $p!$ (every integer $1\le m\le p$ is a factor of $p!$). Then the number of $a$'s becomes $p-m+m\cdot i=p-m+m+p!=p+p!.$ So $x{y}^{i}z=a^{p+p!}{b}^{p+p!}$, which has equal counts of $a$ and $b$ — hence $\notin L$ (recall $L$ requires $n\ne m$). Contradiction with condition 3. $\Rightarrow L$ not regular. $■$

Look at the figure: the $a$-count starts at $p$ (chalk-blue), and each extra copy of $y=a^m$ adds $m$; the pale-yellow choice $i=1+p!/m$ lands the count exactly on $p+p!$, matching the fixed $b$-count and killing the inequality.

Alternative (cleaner): use closure — $L^c$ (complement) intersected with $a^{\ast }{b}^{\ast }$ gives $\{a^n{b}^n\}\cup (\text{finite/regular junk})$; since $\{a^n{b}^n\}$ is non-regular and regular languages are closed under complement and intersection, $L$ is non-regular. This avoids the factorial trick entirely.

Believing you choose the split $x,y,z$. You do not — the adversary does. You only choose $w$ (make it depend on $p$) and $i$ (aim it at the membership boundary), and you must defeat every legal split.

Myhill–Nerode Theorem (an if-and-only-if characterisation) and closure properties (transport non-regularity from a known case).