AFTD Auto-Formalizing Theoretical Domains

min_bipartite_cactus_nfa_states_empty

theoremverifiedformalization

The empty language over any alphabet has a bipartite cactus NFA with at most one state.

Statement

theorem min_bipartite_cactus_nfa_states_empty (α : Type*) :
    min_bipartite_cactus_nfa_states (0 : Language α) ≤ 1
Formalizes
arXiv:2610.11717 Lemma 3.3
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • min_bipartite_cactus_nfa_statesThe minimum number of states in an epsilon-free NFA accepting L whose transition graph is a bipartite cactus.
  • nfa_transition_graphThe transition graph of an NFA A has an undirected edge between distinct states u and v if there is a transition from u to v or from v to…
  • simple_graph_is_cactusA simple graph is a cactus if any two simple cycles that share an edge have identical edge sets (every edge belongs to at most one simple…
  • is_bipartite_cactus_nfaAn NFA A is a bipartite cactus automaton if its undirected transition graph is a cactus and 2-colorable.

Read back from the Lean

For any type α, the minimum number of states in a bipartite cactus NFA accepting the empty language 0 : Language α is at most 1.

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

To prove that the empty language has a bipartite cactus NFA with at most one state, we explicitly construct an NFA on the singleton state space Unit with no transitions, start states, or accept states. This automaton accepts no words, and its transition graph is the empty graph ⊥ on one vertex. The empty graph is vacuously a cactus graph and is 2-colorable, which certifies that 1 is in the set of valid state counts, so the infimum of the set is at most 1.

  1. 1 is the cardinality of a bipartite cactus NFA accepting the empty language, provided our candidate NFA has the right language and graph properties.

    We exhibit a candidate NFA with state type Unit, having no transitions, no start states, and no accept states. The state space Unit has cardinality 1 by Fintype.card_unit. This leaves two obligations: verifying that the NFA accepts the empty language, and that it is a bipartite cactus NFA.

    lines 4–6

    uses Fintype.card_unit

      have hm : 1 ∈ { k : ℕ | ∃ (σ : Type) (_ : Fintype σ) (A : NFA α σ),
          Fintype.card σ = k ∧ A.accepts = (0 : Language α) ∧ is_bipartite_cactus_nfa A } := by
        refine ⟨Unit, inferInstance, ⟨fun _ _ => ∅, ∅, ∅⟩, Fintype.card_unit, ?_, ?_⟩
  2. The candidate NFA accepts the empty language.

    By definition, 0 is the empty set of words (Language.zero_def). By extensionality on an arbitrary word x, since the NFA has no start states and no accept states, no word is accepted, matching the empty set.

    lines 7–9

    uses Language.zero_def, NFA.accepts

        · rw [Language.zero_def]
          ext x
          simp [NFA.accepts]
  3. The transition graph of the candidate NFA is the empty graph ⊥ on Unit.

    Unfolding the definition of a bipartite cactus NFA, we need to examine its transition graph. We show by extensionality on vertices that the transition graph has no edges: an edge requires a transition between states, but the transition function is identically empty. Thus the graph is ⊥, and we rewrite the goal with this fact.

    lines 10–14

    uses SimpleGraph.fromRel

        · dsimp [is_bipartite_cactus_nfa]
          have hbot : nfa_transition_graph (⟨fun _ _ => ∅, ∅, ∅⟩ : NFA α Unit) = ⊥ := by
            ext a b
            simp [nfa_transition_graph, SimpleGraph.fromRel]
          rw [hbot]
  4. The empty graph on Unit is a cactus graph.

    A graph is a cactus if any two cycles sharing an edge are identical as subgraphs. Suppose we have cycles p₁ and p₂ in ⊥ sharing an edge. By case analysis on p₁, a cycle cannot be the trivial empty walk nil, nor can it start with an edge since ⊥ has no edges. Both cases yield a contradiction via False.elim.

    lines 15–19

    uses False.elim

          constructor
          · intro u1 u2 p1 p2 h1 h2 he
            cases p1 with
            | nil => exact False.elim (h1.ne_nil rfl)
            | cons hadj _ => exact False.elim hadj
  5. The empty graph on Unit is 2-colorable.

    We color the single vertex with 0. The requirement that adjacent vertices have distinct colors holds vacuously because ⊥ contains no edges.

    line 20

    uses False.elim

          · refine ⟨⟨fun _ => 0, fun hadj => False.elim hadj⟩⟩
  6. The minimum number of states in a bipartite cactus NFA for the empty language is at most 1.

    Since 1 belongs to the set of valid state counts, the infimum of this set is at most 1 by Nat.sInf_le.

    line 21

    uses Nat.sInf_le

      exact Nat.sInf_le hm
Fintype.card_unit
The singleton type Unit has cardinality 1.
Language.zero_def
The zero language is the empty set of words.
NFA.accepts
The language of words accepted by an NFA.
SimpleGraph.fromRel
The simple graph constructed from a binary relation.
False.elim
From a contradiction (False), any conclusion follows.
Nat.sInf_le
The infimum of a set of natural numbers is at most any member of that set.

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 empty language has a bipartite cactus NFA with at most one state. -/theorem min_bipartite_cactus_nfa_states_empty (α : Type*) :    min_bipartite_cactus_nfa_states (0 : Language α) ≤ 1 := by  have hm : 1 ∈ { k : ℕ | ∃ (σ : Type) (_ : Fintype σ) (A : NFA α σ),      Fintype.card σ = k ∧ A.accepts = (0 : Language α) ∧ is_bipartite_cactus_nfa A } := by    refine ⟨Unit, inferInstance, ⟨fun _ _ => ∅, ∅, ∅⟩, Fintype.card_unit, ?_, ?_⟩    · rw [Language.zero_def]      ext x      simp [NFA.accepts]    · dsimp [is_bipartite_cactus_nfa]      have hbot : nfa_transition_graph (⟨fun _ _ => ∅, ∅, ∅⟩ : NFA α Unit) = ⊥ := by        ext a b        simp [nfa_transition_graph, SimpleGraph.fromRel]      rw [hbot]      constructor      · intro u1 u2 p1 p2 h1 h2 he        cases p1 with        | nil => exact False.elim (h1.ne_nil rfl)        | cons hadj _ => exact False.elim hadj      · refine ⟨⟨fun _ => 0, fun hadj => False.elim hadj⟩⟩  exact Nat.sInf_le hm
See it in the graphDiscuss this resultChallenge it