is_regular_left_quotient
theoremverifiedformalization
For any word w and regular language L, the left quotient L / w = { u | w ++ u ∈ L } is regular.
Statement
theorem is_regular_left_quotient {α : Type*} {L : Language α} (h : L.IsRegular) (w : List α) : (L.leftQuotient w).IsRegular
- Formalizes
- standard textbook result (automata theory: closure of regular languages under left quotient by a word)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
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 left quotient of a regular language by any word is regular. -/theorem is_regular_left_quotient {α : Type*} {L : Language α} (h : L.IsRegular) (w : List α) : (L.leftQuotient w).IsRegular := by rw [Language.isRegular_iff_finite_range_leftQuotient] at * refine h.subset ?_ rintro - ⟨x, rfl⟩ rw [← Language.leftQuotient_append] exact Set.mem_range_self (w ++ x)