Proving a Language Is Not Regular

The asymmetry: easy to confirm, hard to deny

Showing a language IS regular is, in spirit, a one-shot job: build a single DFA, or write one regular expression, point at it, and you are done. Showing a language is NOT regular is a different beast entirely. You cannot exhibit a machine, and you cannot test every possible machine one by one — there are infinitely many automata, and watching each fail would take forever. So you flip the strategy: instead of hunting for a machine, you argue from a property that EVERY regular language is forced to have, and then show your suspect language flatly lacks it.

Every one of these arguments traces back to the same root fact you met earlier in this ladder — the finite-memory limit of a DFA. A deterministic finite automaton is like a turnstile that only ever remembers which state it is currently parked in, and there are only finitely many states. So any language that demands you remember an UNBOUNDED amount — count without a ceiling, or match an arbitrarily long first half against a second half — cannot be regular, because no fixed-size memory can hold the unbounded thing it needs to track. Keep that one sentence in mind and every proof below becomes a way of making it precise.

You arrive at this guide already holding two of the three standard weapons. The previous guide built the pumping lemma and its adversary game; the first guide of this rung turned closure properties into a proof weapon. This guide is the recipe — how you actually pick a weapon, aim it, and finish a proof — and it ends by being honest about exactly when the pumping lemma quietly fails you, which is what motivates the Myhill-Nerode theorem in the next guide.

The recipe: the pumping lemma game, start to finish

The cleanest way to remember the pumping-lemma proof is as a two-player game where you are the challenger trying to expose the language, and an invisible adversary defends the claim 'this language is regular'. The catch that beginners trip over is WHO chooses WHAT. The lemma reads 'there EXISTS a pumping length p such that for ALL long strings, there EXISTS a split, such that for ALL pump counts...'. That alternation of 'exists' and 'for all' is exactly the rulebook of the game, and getting the turn order right is the whole skill.

1. The adversary picks the pumping length p. You do NOT get to choose it — so you must defeat EVERY possible p. Treat p as an arbitrary unknown positive integer and never assume a specific value.
2. YOU pick one string w in the language with length at least p. This is your one big decision: choose the most rigid, most constrained string you can, so the adversary will have no room to wriggle. The whole proof lives or dies on this choice.
3. The adversary splits w = xyz, obeying the two rules the lemma forces: |y| >= 1 (the middle is non-empty) and |xy| <= p (x and y together sit inside the first p symbols). A clever w shape pins y down to one narrow region — that is why step 2 mattered.
4. YOU pick a pump count i and show x y^i z is NOT in the language, contradicting the lemma. Usually i = 2 (pump up) or i = 0 (pump down, deleting y) does the job. Since this works for every legal split and every p, the language cannot be regular.

Worked example 1: a^n b^n

Let us run the recipe on the textbook canary, the language a^n b^n = { a^n b^n : n >= 0 } — some a's followed by exactly the same number of b's. Step 1: the adversary hands us an unknown pumping length p. Step 2 is the move that wins the game: we choose w = a^p b^p. This is a member of the language (it has p a's and p b's), its length is 2p which is comfortably at least p, and — crucially — its first p symbols are ALL a's. That last fact is the trap we are setting.

Step 3: the adversary splits w = xyz with |y| >= 1 and |xy| <= p. Here is where our choice pays off. Because xy must fit inside the first p symbols, and the first p symbols are all a's, the middle piece y can only be made of a's — say y = a^k for some k between 1 and p. The adversary is cornered: there is no way to make y straddle the a/b boundary or land among the b's. Step 4: we pump. Take i = 2, so we read y one extra time: x y^2 z = a^{p+k} b^p. Now there are p+k a's but still only p b's, and since k >= 1, the counts no longer match — so x y^2 z is NOT in a^n b^n. The lemma promised it would be. Contradiction.

Target string :  w = a^p b^p          (our choice, length 2p)

  positions 1..p   are all 'a'   <-- |xy| <= p forces y in here
  positions p+1..2p are all 'b'

Forced split   :  x = a^(p-k),  y = a^k (k>=1),  z = b^p

Pump up (i=2)  :  x y y z = a^(p-k) a^k a^k b^p = a^(p+k) b^p
                  #a = p+k ,  #b = p ,  and k >= 1  =>  #a > #b
                  ==> NOT of the form a^n b^n   ==> NOT in the language

Lemma said it MUST be in the language.  Contradiction => not regular.

Worked example 2: ww, and the closure shortcut

A harder-feeling language is ww = { ww : w in {a,b}* } — every string that is some block repeated twice, like abab (w = ab) or aabaab (w = aab). To accept it you would have to remember the ENTIRE first half to compare it against the second, and for arbitrarily long w that is unbounded memory. Pumping it directly takes a little care in choosing w (the naive choice a^p a^p = a^{2p} can be pumped and proves nothing). The string that works is w = a^p b a^p b: its first p symbols are a's, so the split forces y = a^k inside that opening block, and pumping to i = 2 gives a^{p+k} b a^p b, which is no longer two equal halves. Contradiction.

But there is a slicker route that skips the fiddly string choice entirely: the closure shortcut. Recall from the first guide that the regular languages are closed under intersection — so if you can intersect your suspect with a known-regular language and land on something already known to be non-regular, the suspect could not have been regular in the first place. This is logical judo: you borrow the contradiction from a language whose status you already trust, usually a^n b^n.

Here is the classic example of the shortcut on a different language. Claim: L = strings over {a,b} with equally many a's as b's is not regular. Suppose, for contradiction, that it were. The regular languages are closed under intersection, so L intersected with the regular language a* b* (all a's, then all b's) would also be regular. But that intersection is EXACTLY { a^n b^n : n >= 0 } — the strings that are all-a's-then-all-b's AND have equal counts. We already proved a^n b^n is not regular, so the intersection is not regular — contradicting closure. Therefore L was not regular. No pumping, no fiddly string; one canonical fact does all the work.

The honest caveat: passing the test proves nothing

Now the most important honesty point in this whole topic. The pumping lemma is a NECESSARY condition for regularity but NOT a SUFFICIENT one. In plain words: 'every regular language can be pumped' is true, but 'every language that can be pumped is regular' is FALSE. Only the FAILURE of the lemma proves anything, and what it proves is non-regularity. If you try to pump a language and it stubbornly keeps pumping no matter what you do, you have learned NOTHING about whether it is regular. You may have simply picked a weak string — or the language may be one of the genuine counterexamples that passes the pumping test yet is not regular.

Why the gap exists is worth seeing. The pumping lemma captures only ONE consequence of finite memory — that long strings must contain a repeatable loop. A devious language can hand you a trivially pumpable structure while still encoding a constraint that finite memory cannot enforce. The standard counterexample is L = { a^i b^j c^k : if i = 1 then j = k } (together with all strings where i is not 1). Every long string in it can be pumped — when i is not 1 you pump in the a-region and stay in; when i = 1, the available split does not threaten the j = k constraint — yet L is genuinely not regular. So writing 'L satisfies the pumping lemma, therefore L is regular' is a flat logical error, never valid.

This is precisely why the next two tools matter. A closure argument can sometimes succeed where a particular pumping attempt stalls, by attacking from a different angle (intersection, complement, reversal, or homomorphism). And the Myhill-Nerode theorem, which the next guide builds, is both necessary AND sufficient — it characterizes regularity EXACTLY, so it never gives a false 'pass' and never fails to detect a genuinely non-regular language. When the pumping lemma leaves you uncertain, Myhill-Nerode is the decisive instrument that settles the question for good.

Choosing your weapon, and common traps

In practice, reach first for whichever tool is shortest for the language in front of you. If the language has an obvious 'count this against that' shape (a^n b^n, palindromes, balanced parentheses), the pumping lemma game with a well-chosen string is fast and direct. If your language is a messy mixture but contains a clean non-regular core once you filter it, the closure shortcut — intersect with a simple regular language to expose a^n b^n — is often a one-line proof. And if both feel slippery, skip straight to Myhill-Nerode: exhibit an infinite family of strings that are pairwise distinguishable, and you are done with certainty.

Three traps catch almost everyone at first. (1) Choosing your own p — the adversary chooses p, and your argument must survive every p, so treat it as an arbitrary unknown. (2) Picking a flabby string in step 2 — w = a^{2p} for a^n b^n lets the adversary pump within the a's and stay legal, so the proof fails through no fault of the lemma; always pick the most CONSTRAINED string, the one whose first p symbols pin y down. (3) Concluding regularity from a successful pump — there is no such thing as 'proving regular by pumping'; only failure-to-pump proves non-regularity, and a string that always pumps just means you chose poorly or need Myhill-Nerode.

Step back and the through-line is simple: every non-regularity proof is a way of catching a language red-handed needing unbounded memory. The finite-memory limit is the crime, the pumping lemma and closure arguments are two different detectives, and Myhill-Nerode is the forensic test that never produces a false negative. Master picking the right string and respecting who-chooses-what, stay honest about the necessary-not-sufficient caveat, and you can prove the boundary of the regular languages with confidence.