The pumping lemma for regular languages
ProvedFamousTheorems.pumping_lemma_regularThe pumping lemma for regular languages. Let be a deterministic finite automaton with states, and a word accepted by of length at least . Then with and nonempty, such that is accepted by for every .
The pumping lemma is the standard tool for proving that a language is not regular, for example or the language of balanced parentheses.
Formalization note. Mathlib's DFA.pumping_lemma. The number of states is Fintype.card σ, and " is accepted for every " is stated as the language inclusion {a} * b* * {c} ≤ M.accepts, where KStar.kstar {b} is the Kleene star of the singleton language.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem pumping_lemma_regular {α σ : Type*} (M : DFA α σ) [Fintype σ] {x : List α} (hx : x ∈ M.accepts) (hlen : Fintype.card σ ≤ x.length) :
∃ a b c : List α, x = a ++ b ++ c ∧ a.length + b.length ≤ Fintype.card σ ∧ b ≠ [] ∧
({a} : Language α) * KStar.kstar ({b} : Language α) * ({c} : Language α) ≤ M.accepts := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `DFA.pumping_lemma`. Proof here reduces to that Mathlib result.