Pumping lemma for regular languages

Mathematical statement

Keep the quantifier order: there exists p, for every w in L with |w|≥p, there exist x,y,z, for every i≥0, with w=xyz, |xy|≤p, |y|>0 and xy^i z in L. Positive regular families use a repeated-state loop in a complete DFA run and a symbolic invariant for every i, not a few pump tests. For L={a^n b^n}, choose w=a^p b^p and address every legal split: y consists only of a symbols, so i=0 leaves the language. One decomposition, bounded words or finite checks do not prove regularity. The adversary chooses the word before the prover chooses the split and the adversary chooses i after that.

Representative formula (exact TeX)

P(L,p,w)=b

Assumptions

• p is a positive integer and word/split indices are exact.
• A positive witness uses a complete DFA state loop and an invariant for all pump counts.
• A negative adversary addresses every split satisfying |xy|≤p and |y|>0.

Symbol scope

• P — regular-pumping operator
• L — formal language
• p — pumping length
• w — sufficiently long member word
• b — pumping-property statement

Intuition, definition, and misconceptions

Check the whole quantifier order and split constraints first.

A DFA loop supports every i, not merely finitely tested pump counts.

The a^p b^p adversary addresses all legal splits.

One pumpable split does not prove regularity, and one unfavorable preselected split does not prove nonregularity.

Adopted derivation guide

The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.

Prerequisites

• Regular language — Specify the applicable class.
• Deterministic finite automaton — Supply the repeated-state loop.
• Mathematical proof — Use contradiction and quantifier opposition.
• Pigeonhole principle — Obtain a repeated state among p+1 positions.
• Quantifiers and explicit domains — Retain the adversarial choice order.
• Mathematical induction — Retain the run invariant for every pump count.

Verification boundary

The pumping property is necessary, not sufficient, for regularity. Fixed-p split tables do not alone replace the argument for every proposed pumping length.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.

Next obligation

Add Myhill–Nerode and context-free pumping boundaries.

Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.