AFTD Auto-Formalizing Theoretical Domains

is_regular_one

theoremverifiedformalization

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.

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

    lines 3–11

    uses List.foldl_cons, if_false

      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
  2. 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}.

    line 12

      refine ⟨Bool, inferInstance, ⟨fun _ _ => false, true, {true}⟩, ?_⟩
  3. 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.

    lines 13–15

    uses DFA.mem_accepts, Language.mem_one

      ext x
      rw [DFA.mem_accepts, Language.mem_one]
      show List.foldl (fun (_ : Bool) (_ : α) => false) true x ∈ ({true} : Set Bool) ↔ x = []
  4. 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.

    lines 16–17

      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 [].

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

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