Arden's lemma
ProvedFamousTheorems.arden_lemmaArden's lemma. Let be languages over an alphabet with the empty word not in . Then solves the equation
if and only if . So is the unique solution.
It is the standard tool for solving systems of language equations. It gives the conversion of finite automata into regular expressions (Brzozowski's algebraic method) and is basic in the algebraic theory of regular languages.
Formalization note. Mathlib's Language.self_eq_mul_add_iff. In Language α, + is union, * is concatenation, and KStar.kstar m is the Kleene star . The hypothesis [] ∉ m excludes the empty word.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem arden_lemma {α : Type*} {l m n : Language α} (hm : [] ∉ m) : l = m * l + n ↔ l = KStar.kstar m * n := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Language.self_eq_mul_add_iff`. Proof here reduces to that Mathlib result.