AFTD Auto-Formalizing Theoretical Domains

is_regular_pow

theoremverifiedformalization

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.

  1. 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.

    lines 3–4

    uses pow_zero, is_regular_one

      induction n with
      | zero => rw [pow_zero]; exact is_regular_one
  2. 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.

    line 5

    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

/-- 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
See it in the graphDiscuss this resultChallenge it