AFTD Auto-Formalizing Theoretical Domains

is_regular_diff

theoremverifiedformalization

The difference L1 \\ L2 of two regular languages is regular.

Statement

theorem is_regular_diff {α : Type*} {L1 L2 : Language α} (h1 : L1.IsRegular) (h2 : L2.IsRegular) : (L1 \ L2).IsRegular
Formalizes
standard textbook result (automata theory: closure of regular languages under difference)
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

Lean source view module on GitHub

/-- Regular languages are closed under set difference. -/theorem is_regular_diff {α : Type*} {L1 L2 : Language α} (h1 : L1.IsRegular) (h2 : L2.IsRegular) : (L1 \ L2).IsRegular := by  rw [sdiff_eq]  exact h1.inf h2.compl
See it in the graphDiscuss this resultChallenge it