Artificial Intelligence & Data Science is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Pumping lemma for regular languages

Pumping lemma for regular languages gives a necessary property of every regular language and is used to prove some languages are not regular.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Engineers use the pumping lemma when they must prove that a given pattern is not implementable by a finite-state controller (a DFA) — for example, to show that some protocol or simple parser requires more memory than a finite automaton can give. It is a standard theoretical tool to separate regular languages (handled by finite automata, regular expressions) from non-regular ones, guiding design choices (use a stack/PDAs or Turing machine instead).

Key ideas

  • Language: a set of strings over an alphabet.
  • Deterministic finite automaton (DFA): a 5-tuple (Q, Σ, δ, q0, F) where Q is a finite set of states, Σ an alphabet, δ: Q×Σ → Q the transition function, q0 ∈ Q the start state, and F ⊆ Q the set of accepting states.
  • Regular language: a language that is accepted by some DFA (equivalently expressible by a regular expression or right-linear or left-linear grammar).

Exact statement (standard pumping lemma for regular languages):

  • Pumping lemma: If L is a regular language, then there exists an integer p ≥ 1 (called the pumping length) such that for every string s ∈ L with |s| ≥ p, we can write s = x y z satisfying:
    1. |y| > 0,
    2. |x y| ≤ p,
    3. for all integers i ≥ 0, the string x y^i z ∈ L.

Explanation of the statement and assumptions:

  • The lemma assumes L is regular (there exists a DFA accepting L).
  • The integer p depends on the chosen DFA for L (one can take p to be the number of states of any DFA that accepts L, for example a minimal DFA). This p depends only on L (not on s), and once you fix a DFA for L, p is fixed.
  • For every sufficiently long string s from L (|s| ≥ p), there exists a decomposition x,y,z meeting the three properties above. Note: the lemma guarantees the existence of at least one such decomposition for every s, not that every possible decomposition works.

Sketch proof (the standard DFA / pigeonhole argument) — give this in exam answers step by step:

  1. Let L be regular. Let M = (Q, Σ, δ, q0, F) be a DFA that accepts L. Let p = |Q| (number of states).
  2. Take any string s ∈ L with |s| ≥ p. Run M on s and record the sequence of states visited, starting from q0, after reading each prefix of s. There are |s| + 1 ≥ p + 1 visited states (including the start state before reading any symbol).
  3. By the pigeonhole principle, among the first p + 1 visited states there must be two equal states: say the state after reading prefix of length i equals the state after reading prefix of length j, with 0 ≤ i < j ≤ p.
  4. Let x be the prefix of length i, let y be the substring from position i+1 to j (length j − i > 0), and let z be the remaining suffix. Then s = x y z, |y| > 0 and |x y| = j ≤ p (so |x y| ≤ p).
  5. Because reading y takes the DFA from state q to the same state q (a loop), repeating y any number of times keeps the DFA in the same state at that point; therefore for all i ≥ 0, x y^i z is also accepted by M. So x y^i z ∈ L.
  6. This proves the pumping lemma.

What to draw for the usual exam diagram (describe precisely):

  • Draw a row of DFA states as nodes q0 → q1 → ... → qk with directed edges labeled by the symbols of s in order. Mark the repeated state (two nodes in the prefix segment with the same label) and draw a loop from the first occurrence to the second; label the segment from start to first occurrence as x, the loop segment as y, and the rest as z. Label p = |Q| and show indices i and j with j ≤ p.

Important logical point students miss: The adversary (exam grader / nature) chooses the decomposition x,y,z that satisfies the lemma conditions; your proof by contradiction must show that for every possible decomposition satisfying |y|>0 and |x y| ≤ p, there exists some i (typically 0 or 2) for which x y^i z ∉ L.

Limitations and alternatives:

  • The pumping lemma is a necessary condition for regularity, not sufficient. That means: a language that satisfies the pumping property may or may not be regular; you cannot use the lemma to prove regularity. For sufficiency you use Myhill–Nerode theorem or construct a DFA/regular expression.
  • Other tools often used with or instead of the pumping lemma: closure properties of regular languages (union, intersection with regular sets, complement), Myhill–Nerode minimisation, and direct DFA/regex construction.

Formulas

|y| > 0 — y is a non-empty substring in the decomposition s = x y z. (Here |·| is string length, unitless.)

|x y| ≤ p — the pumpable part y occurs within the first p symbols of s. p is the pumping length (an integer ≥ 1).

∀ i ≥ 0 : x y^i z ∈ L — repeating y i times yields a string still in L, for all non-negative integers i.

(Notation: y^i means y concatenated i times; y^0 is the empty string ε.)

Worked examples

Example 1 — classic: Prove L = { a^n b^n | n ≥ 0 } is not regular. Model answer (step-by-step):

  1. Assume, for contradiction, that L is regular. Let p be the pumping length given by the pumping lemma.
  2. Choose s = a^p b^p. Clearly s ∈ L and |s| = 2p ≥ p.
  3. By the lemma, s can be written s = x y z with |y| > 0 and |x y| ≤ p.
  4. Because |x y| ≤ p, the substring x y lies entirely inside the first block of a's. So y = a^k for some k ≥ 1.
  5. Pump with i = 0 to get x y^0 z = x z. That removes k a's, so x z = a^{p-k} b^p.
  6. But a^{p-k} b^p has fewer a's than b's (p − k < p), so x z ∉ L. This contradicts the pumping lemma requirement that x y^0 z ∈ L.
  7. Therefore the assumption that L is regular is false. Conclude: L is not regular.

Final line (exam style): Hence L = { a^n b^n } is not regular. (Bold this conclusion on an answer sheet.)

Example 2 — another standard: Prove L = { 0^n 1^n 0^n | n ≥ 0 } is not regular. Model answer:

  1. Assume L is regular and let p be the pumping length.
  2. Choose s = 0^p 1^p 0^p, so s ∈ L and |s| = 3p ≥ p.
  3. Decompose s = x y z with |y| > 0 and |x y| ≤ p.
  4. Since |x y| ≤ p, y lies entirely inside the first block of 0's, so y = 0^k with k ≥ 1.
  5. Pump with i = 0: x y^0 z removes k zeros from the first block, giving 0^{p-k} 1^p 0^p.
  6. Now the first and last zero-block lengths differ (p − k ≠ p), so x y^0 z ∉ L.
  7. This contradicts the pumping lemma, so L is not regular.

(Exam tip: explicitly state why y must be within the first block because |x y| ≤ p.)

Example 3 — showing pumping lemma does not prove regularity (short):

  • Let L = a* b* (all strings of some a's followed by some b's). L is regular (regular expression a* b*). You cannot use the pumping lemma to prove regularity; instead show a DFA or regex. This reminds examiners you know the lemma is only necessary, not sufficient.

Common mistakes

  • Forgetting that the decomposition x,y,z is chosen adversarially — proofs must work for every possible decomposition meeting |y| > 0 and |x y| ≤ p.
  • Assuming |y| = 1 (it can be any positive length) or forgetting to use the fact |x y| ≤ p to restrict where y lies.
  • Mixing pumping lemma for regular languages with the pumping lemma for context-free languages (they are different statements).

For your exam

Kinds of questions you will see:

  • State and prove the pumping lemma for regular languages (short proof via DFA + pigeonhole).
  • Use the pumping lemma to prove a specific language is not regular (model answers as above).
  • Explain limitations of the lemma and compare with Myhill–Nerode (short note).
  • Draw and label the DFA path used in the lemma proof.

What a full-marks answer includes:

  • Precise statement of the pumping lemma (with p, x,y,z, and the three properties).
  • A correct proof sketch from the DFA using the pigeonhole principle (clearly define p = |Q| and argue repetition of states).
  • For non-regularity proofs: explicit choice of s (|s| ≥ p), then argument covering all possible decompositions satisfying the lemma constraints and picking an i giving contradiction (show resulting string not in L). Conclude clearly.
  • If asked for regularity, construct a DFA or give a regular expression (do not attempt to "prove regularity" by pumping lemma).

Quick check

  1. State the three conditions in the pumping lemma (short).
  2. Why must |y| > 0 in the pumping lemma proof from a DFA?
  3. Is the pumping lemma sufficient to prove a language is regular? Answer briefly.

Answers: 1) |y| > 0; |x y| ≤ p; ∀ i ≥ 0, x y^i z ∈ L. 2) Because the repeated states give a positive-length loop (j > i), so the loop segment y has length > 0. 3) No — pumping lemma is necessary but not sufficient; to prove regularity construct a DFA or use Myhill–Nerode.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?