is_regular_one
The language {[]} containing only the empty word is regular.
Statement
theorem is_regular_one {α : Type*} : (1 : Language α).IsRegular
- Formalizes
- standard textbook result (automata theory): {ε} is regular
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- is_regular_powFor any regular language L and natural number n, the n-th power L^n is regular.
The proof, explained
The theorem proves that the unit language 1 = {[]} is regular by explicitly constructing a deterministic finite automaton with two states (the booleans). The DFA starts in the accepting state true and transitions to the sink state false on any input symbol. An auxiliary induction lemma (`hfold`) verifies that processing any non-empty word sends the automaton to false while the empty word leaves it in true, so exactly the empty word is accepted.
For any word y and boolean state s, folding the transition function that always returns false over y starting from s yields s if y = [] and false otherwise.
We prove the auxiliary lemma `hfold` by induction on the word y. In the base case y = [], the fold immediately returns the initial state s, matching the if-condition since [] = []. In the inductive step y = b :: y', `List.foldl_cons` rewrites the fold to one over y' starting from false. By the induction hypothesis, folding from false over y' yields false regardless of whether y' is empty; since b :: y' is non-empty, the target if-expression also evaluates to false via `if_false`.
uses
List.foldl_cons,if_falsehave hfold : ∀ (y : List α) (s : Bool), List.foldl (fun (_ : Bool) (_ : α) => false) s y = if y = [] then s else false := by intro y induction y with | nil => intro s; simp | cons b y ih => intro s simp only [List.foldl_cons, ih, reduceCtorEq, if_false] split_ifs <;> rfl
To show that the language 1 is regular, it suffices to construct a two-state DFA that accepts 1.
By definition, a language is regular if it is recognized by a DFA with a finite state type. We instantiate the DFA with states `Bool` (which is finite), the transition function mapping every state and symbol to false, initial state true, and accepting set {true}.
refine ⟨Bool, inferInstance, ⟨fun _ _ => false, true, {true}⟩, ?_⟩
A word x is accepted by the DFA if and only if x ∈ 1, which reduces to showing that folding the transition function from true along x yields true if and only if x = [].
By language extensionality (`ext x`), we consider an arbitrary word x. Using `DFA.mem_accepts`, acceptance of x means the state reached after evaluating x from true is in {true}. By `Language.mem_one`, x ∈ 1 means x = []. The `show` line unfolds DFA evaluation to a left fold of the transition function across x starting from true.
uses
DFA.mem_accepts,Language.mem_oneext x rw [DFA.mem_accepts, Language.mem_one] show List.foldl (fun (_ : Bool) (_ : α) => false) true x ∈ ({true} : Set Bool) ↔ x = []
The DFA accepts x if and only if x = [], completing the proof that 1 is regular.
Rewriting with `hfold`, the state reached after processing x simplifies to `if x = [] then true else false`. We split into cases on whether x = []: if x = [], the state is true ∈ {true}, which simplifies to true ↔ true; if x ≠ [], the state is false ∈ {true}, which simplifies to false ↔ false. Both cases simplify to true equivalences.
rw [hfold] split_ifs with h <;> simp [h]
List.foldl_cons- Folding a function over a cons cell `a :: l` starting from `b` equals folding over `l` starting from `f b a`.
if_false- An if-then-else expression whose condition is false evaluates to its second branch.
DFA.mem_accepts- A word is accepted by a DFA if and only if the state reached after evaluating the word from the start state belongs to the accept set.
Language.mem_one- A word belongs to the unit language 1 if and only if it is the empty list [].
- In line 12, the finiteness of the DFA state type `Bool` is supplied automatically via typeclass inference (`inferInstance`). Line 15 is a definitional elaboration (`show`) that makes explicit that DFA evaluation along a word is computed by a left fold (`List.foldl`).
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.
/-- The language containing only the empty word (the unit language 1) is regular. -/theorem is_regular_one {α : Type*} : (1 : Language α).IsRegular := by have hfold : ∀ (y : List α) (s : Bool), List.foldl (fun (_ : Bool) (_ : α) => false) s y = if y = [] then s else false := by intro y induction y with | nil => intro s; simp | cons b y ih => intro s simp only [List.foldl_cons, ih, reduceCtorEq, if_false] split_ifs <;> rfl refine ⟨Bool, inferInstance, ⟨fun _ _ => false, true, {true}⟩, ?_⟩ ext x rw [DFA.mem_accepts, Language.mem_one] show List.foldl (fun (_ : Bool) (_ : α) => false) true x ∈ ({true} : Set Bool) ↔ x = [] rw [hfold] split_ifs with h <;> simp [h]