min_bipartite_cactus_nfa_states_empty
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 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.
uses
Fintype.card_unithave 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, ?_, ?_⟩
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.
uses
Language.zero_def,NFA.accepts· rw [Language.zero_def] ext x simp [NFA.accepts]
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.
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]
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.
uses
False.elimconstructor · 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
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.
uses
False.elim· refine ⟨⟨fun _ => 0, fun hadj => False.elim hadj⟩⟩
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.
uses
Nat.sInf_leexact 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
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 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