is_regular_pow
For any regular language L and natural number n, the n-th power L^n is regular.
Statement
theorem is_regular_pow {α : Type*} {L : Language α} (h : L.IsRegular) (n : ℕ) : (L ^ n).IsRegular
- Formalizes
- Sipser, Exercise 1.31
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- is_regular_mulThe concatenation of two regular languages is regular.
- is_regular_oneThe language {[]} containing only the empty word is regular.
Read back from the Lean
For any type α and any formal language L over alphabet α (L : Language α, i.e., a set of lists of elements of α), if L is regular (L.IsRegular), then for every natural number n, the n-th power L ^ n (the language formed by the concatenation of n words from L, with L ^ 0 = {[]}) is also regular.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
We proceed by induction on the exponent n. In the base case n = 0, L^0 simplifies to the language 1, which is regular. For the inductive step, L^(n + 1) expands to L^n * L, which is regular by the induction hypothesis and the closure of regular languages under concatenation.
The base case holds: L^0 is regular.
We argue by induction on the exponent n. In the base case n = 0, the power L^0 rewrites to the language 1 by pow_zero. The language 1 is regular by is_regular_one.
uses
pow_zero,is_regular_oneinduction n with | zero => rw [pow_zero]; exact is_regular_one
The inductive step holds: if L^n is regular, then L^(n + 1) is regular.
Assuming the induction hypothesis (ih) that L^n is regular, we rewrite L^(n + 1) as L^n * L using pow_succ. By is_regular_mul, the product of regular languages is regular, so L^n * L is regular because L^n is regular by ih and L is regular by the assumption h.
uses
pow_succ,is_regular_mul| succ n ih => rw [pow_succ]; exact is_regular_mul ih h
pow_zero- In any monoid, any element raised to the power 0 is the identity element 1.
is_regular_one- The trivial language 1 (containing only the empty string) is regular.
pow_succ- In any monoid, raising an element to the power n + 1 equals the n-th power multiplied by the element.
is_regular_mul- The concatenation (product) of two regular languages is regular.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Any power of a regular language is regular. -/theorem is_regular_pow {α : Type*} {L : Language α} (h : L.IsRegular) (n : ℕ) : (L ^ n).IsRegular := by induction n with | zero => rw [pow_zero]; exact is_regular_one | succ n ih => rw [pow_succ]; exact is_regular_mul ih h