AFTD Auto-Formalizing Theoretical Domains

regular_expression_exists_parity_normal_form

theoremverifiedformalization

For every regular expression r there are regular expressions r₀ and r₁, typed with parity 0 and 1 respectively, with L(r₀) = {w ∈ L(r) : |w| even} and L(r₁) = {w ∈ L(r) : |w| odd}; in particular every star in r₀ or r₁ is applied to an expression of parity 0.

Statement

theorem regular_expression_exists_parity_normal_form {α : Type*} (r : RegularExpression α) :
    ∃ r₀ r₁ : RegularExpression α,
      regular_expression_typed_parity r₀ 0 ∧ regular_expression_typed_parity r₁ 1 ∧
      (∀ w, w ∈ r₀.matches' ↔ w ∈ r.matches' ∧ w.length % 2 = 0) ∧
      (∀ w, w ∈ r₁.matches' ↔ w ∈ r.matches' ∧ w.length % 2 = 1)
Formalizes
arXiv:2610.11717 (Every Regular Language Has a Bipartite Cactus Automaton), Lemma 3.1 (parity normal form).
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

The proof, explained

The theorem is proved by constructing a pair of regular expressions (r₀, r₁) by structural induction on r via the recursive function `regular_expression_parity_split`. For the base cases and alternation, the split distributes directly, while for concatenation the components are combined according to the addition table of ℤ/2ℤ. In the Kleene star case r = u*, the subexpressions u₀ and u₁ are rearranged into r₀ = u₀* (u₁ u₀* u₁ u₀*)* and r₁ = u₀* u₁ u₀* (u₁ u₀* u₁ u₀*)*, ensuring that every star is applied to an expression of typed parity 0. The language equivalence for u* is established using Kleene algebra identities, with the reverse inclusion proved via the right star induction rule `kstar_le_of_mul_le_right`.

  1. In the ring ℤ/2ℤ, 1 + 1 = 0.

    Established by the decision procedure `decide`, which evaluates 1 + 1 = 0 in the two-element ring ℤ/2ℤ.

    line 35

      have h11 : (1 : ZMod 2) + 1 = 0 := by decide
  2. The split specification holds for the base case r = 0.

    By induction on r. When r = 0, the function returns (0, 0). Both components satisfy typed parity trivially by definition. No word belongs to the empty language 0 (by `Language.notMem_zero`), so the language equivalences reduce to False ↔ False.

    lines 36–40

    uses Language.notMem_zero

      induction r with
      | zero =>
        refine ⟨trivial, trivial, fun w => ?_, fun w => ?_⟩ <;>
        · change w ∈ (0 : Language α) ↔ w ∈ (0 : Language α) ∧ _
          simp [Language.notMem_zero]
  3. The split specification holds for the base case r = ε.

    For r = ε, the split is (1, 0). The regular expression 1 has typed parity 0, and 0 trivially has typed parity 1. By `Language.mem_one`, the language 1 matches only the empty word [], which has length 0 (even), proving the parity 0 equivalence. For parity 1, the equivalence reduces to False on both sides using `Language.notMem_zero`, `false_iff`, and `not_and`.

    lines 41–52

    uses Language.mem_one, Language.notMem_zero, false_iff, not_and

      | epsilon =>
        refine ⟨rfl, trivial, fun w => ?_, fun w => ?_⟩
        · change w ∈ (1 : Language α) ↔ w ∈ (1 : Language α) ∧ _
          rw [Language.mem_one]
          constructor
          · rintro rfl; simp
          · exact fun h => h.1
        · change w ∈ (0 : Language α) ↔ w ∈ (1 : Language α) ∧ _
          rw [Language.mem_one]
          simp only [Language.notMem_zero, false_iff, not_and]
          rintro rfl
          simp
  4. The split specification holds for the base case r = a (a single character).

    For a single character a, the split is (0, char a). Parity 0 holds trivially for 0, while char a has typed parity 1 by definition. The language of char a contains only the single-character word [a], which has length 1 (odd). Thus no word has even length (satisfying the parity 0 condition vacuously via `Language.notMem_zero`, `false_iff`, and `not_and`), and every matching word has odd length (establishing parity 1).

    lines 53–68

    uses Language.notMem_zero, false_iff, not_and

      | char a =>
        refine ⟨trivial, rfl, fun w => ?_, fun w => ?_⟩
        · change w ∈ (0 : Language α) ↔ w ∈ ({[a]} : Language α) ∧ _
          simp only [Language.notMem_zero, false_iff, not_and]
          intro h
          replace h : w = [a] := h
          subst h
          simp
        · change w ∈ ({[a]} : Language α) ↔ w ∈ ({[a]} : Language α) ∧ _
          constructor
          · intro h
            refine ⟨h, ?_⟩
            replace h : w = [a] := h
            subst h
            simp
          · exact fun h => h.1
  5. The split specification holds for alternation r = u + v.

    By the induction hypotheses on u and v, both u₀ and v₀ have typed parity 0, and both u₁ and v₁ have typed parity 1; by definition of typed parity for sums, u₀ + v₀ and u₁ + v₁ have typed parity 0 and 1 respectively. Using `Language.mem_add` to rewrite membership in a sum of languages as a disjunction, the induction hypotheses show that matching u₀ + v₀ is equivalent to matching u + v with even length, and similarly for odd length, closed by propositional reasoning (`tauto`).

    lines 69–78

    uses Language.mem_add

      | plus u v ihu ihv =>
        obtain ⟨tu0, tu1, mu0, mu1⟩ := ihu
        obtain ⟨tv0, tv1, mv0, mv1⟩ := ihv
        refine ⟨⟨tu0, tv0⟩, ⟨tu1, tv1⟩, fun w => ?_, fun w => ?_⟩
        · change w ∈ _ + _ ↔ w ∈ u.matches' + v.matches' ∧ _
          rw [Language.mem_add, Language.mem_add, mu0, mv0]
          tauto
        · change w ∈ _ + _ ↔ w ∈ u.matches' + v.matches' ∧ _
          rw [Language.mem_add, Language.mem_add, mu1, mv1]
          tauto
  6. The split specification holds for concatenation r = u · v.

    The even component is u₀ v₀ + u₁ v₁ and the odd component is u₀ v₁ + u₁ v₀. Typed parities follow from addition in ℤ/2ℤ: 0 + 0 = 0 and 1 + 1 = 0 (using h11) for parity 0, and 0 + 1 = 1 and 1 + 0 = 1 for parity 1. By `Language.mem_add` and `Language.mem_mul`, a word w matches a concatenation iff w = a ++ b with a ∈ L(u) and b ∈ L(v). By `List.length_append`, |w| = |a| + |b|. Splitting on |a| % 2 ∈ {0, 1} via `Nat.mod_two_eq_zero_or_one` into `Or.inl` and `Or.inr`, linear arithmetic (`omega`) confirms that |w| is even iff |a| and |b| have the same parity, and odd iff they have opposite parity.

    lines 79–103

    uses Language.mem_add, Language.mem_mul, List.length_append, Nat.mod_two_eq_zero_or_one, Or.inl, Or.inr

      | comp u v ihu ihv =>
        obtain ⟨tu0, tu1, mu0, mu1⟩ := ihu
        obtain ⟨tv0, tv1, mv0, mv1⟩ := ihv
        refine ⟨⟨⟨0, 0, by decide, tu0, tv0⟩, ⟨1, 1, h11, tu1, tv1⟩⟩,
          ⟨⟨0, 1, by decide, tu0, tv1⟩, ⟨1, 0, by decide, tu1, tv0⟩⟩, fun w => ?_, fun w => ?_⟩
        · change w ∈ _ * _ + _ * _ ↔ w ∈ u.matches' * v.matches' ∧ _
          simp only [Language.mem_add, Language.mem_mul, mu0, mu1, mv0, mv1]
          constructor
          · rintro (⟨a, ⟨ha, ha'⟩, b, ⟨hb, hb'⟩, rfl⟩ | ⟨a, ⟨ha, ha'⟩, b, ⟨hb, hb'⟩, rfl⟩) <;>
            exact ⟨⟨a, ha, b, hb, rfl⟩, by simp [List.length_append]; omega⟩
          · rintro ⟨⟨a, ha, b, hb, rfl⟩, hw⟩
            rw [List.length_append] at hw
            rcases Nat.mod_two_eq_zero_or_one a.length with h | h
            · exact Or.inl ⟨a, ⟨ha, h⟩, b, ⟨hb, by omega⟩, rfl⟩
            · exact Or.inr ⟨a, ⟨ha, h⟩, b, ⟨hb, by omega⟩, rfl⟩
        · change w ∈ _ * _ + _ * _ ↔ w ∈ u.matches' * v.matches' ∧ _
          simp only [Language.mem_add, Language.mem_mul, mu0, mu1, mv0, mv1]
          constructor
          · rintro (⟨a, ⟨ha, ha'⟩, b, ⟨hb, hb'⟩, rfl⟩ | ⟨a, ⟨ha, ha'⟩, b, ⟨hb, hb'⟩, rfl⟩) <;>
            exact ⟨⟨a, ha, b, hb, rfl⟩, by simp [List.length_append]; omega⟩
          · rintro ⟨⟨a, ha, b, hb, rfl⟩, hw⟩
            rw [List.length_append] at hw
            rcases Nat.mod_two_eq_zero_or_one a.length with h | h
            · exact Or.inl ⟨a, ⟨ha, h⟩, b, ⟨hb, by omega⟩, rfl⟩
            · exact Or.inr ⟨a, ⟨ha, h⟩, b, ⟨hb, by omega⟩, rfl⟩
  7. For r = u*, the candidate expressions r₀ and r₁ have typed parity 0 and 1, respectively, and all words they match have the corresponding length parity.

    Let u₀ and u₁ be the split components of u. Defining C = u₁ u₀* u₁ u₀*, its typed parity is 0 because 1 + 0 + 1 + 0 = 0 in ℤ/2ℤ (using h11). Then r₀ = u₀* C* has typed parity 0 + 0 = 0, and r₁ = u₀* u₁ u₀* C* has typed parity 0 + 1 + 0 + 0 = 1. Applying `regular_expression_typed_parity_length`, any word matching r₀ has length congruent to 0 mod 2, and any word matching r₁ has length congruent to 1 mod 2; `ZMod.val_natCast` translates this congruence into equality modulo 2.

    lines 104–124

    uses regular_expression_parity_split, regular_expression_typed_parity_length, ZMod.val_natCast

      | star u ihu =>
        obtain ⟨tu0, tu1, mu0, mu1⟩ := ihu
        simp only [regular_expression_parity_split]
        set u0 := (regular_expression_parity_split u).1 with hu0
        set u1 := (regular_expression_parity_split u).2 with hu1
        have tc : regular_expression_typed_parity
            (u1 * RegularExpression.star u0 * u1 * RegularExpression.star u0) 0 :=
          ⟨0, 0, by decide, ⟨1, 1, h11, ⟨1, 0, by decide, tu1, ⟨rfl, tu0⟩⟩, tu1⟩, ⟨rfl, tu0⟩⟩
        have tA : regular_expression_typed_parity (RegularExpression.star u0 *
            RegularExpression.star (u1 * RegularExpression.star u0 * u1 *
              RegularExpression.star u0)) 0 :=
          ⟨0, 0, by decide, ⟨rfl, tu0⟩, ⟨rfl, tc⟩⟩
        have tB : regular_expression_typed_parity (RegularExpression.star u0 * u1 *
            RegularExpression.star u0 * RegularExpression.star (u1 * RegularExpression.star u0 * u1 *
              RegularExpression.star u0)) 1 :=
          ⟨1, 0, by decide, ⟨1, 0, by decide, ⟨0, 1, by decide, ⟨rfl, tu0⟩, tu1⟩, ⟨rfl, tu0⟩⟩,
            ⟨rfl, tc⟩⟩
        have pA := regular_expression_typed_parity_length _ 0 tA
        have pB := regular_expression_typed_parity_length _ 1 tB
        have toMod : ∀ (n : ℕ) (p : ZMod 2), (n : ZMod 2) = p → n % 2 = p.val := fun n p h => by
          rw [← h, ZMod.val_natCast]
  8. The languages of r₀ and r₁ are contained in L(u)*: D C* ≤ U* and D U₁ D C* ≤ U*.

    In the idempotent semiring of languages, let U = L(u), U₀ = L(u₀), U₁ = L(u₁), D = U₀*, and C = U₁ D U₁ D. The induction hypotheses give U₀ ≤ U and U₁ ≤ U. Monotonicity (`kstar_mono`) and sublanguage inclusion (`le_kstar`) yield D ≤ U* and U₁ ≤ U*. Combining these with `kstar_mul_kstar` gives C ≤ (U*)^4 = U*, and idempotence (`kstar_idem`) gives C* ≤ U*. Hence D C* ≤ U* U* = U* and D U₁ D C* ≤ (U*)^4 = U*. Furthermore, 1 ≤ D and 1 ≤ C* by `one_le_kstar`.

    lines 125–153

    uses Language.mem_add, Nat.mod_two_eq_zero_or_one, Or.inl, Or.inr, kstar_idem, kstar_mono, kstar_mul_kstar, le_kstar, one_le_kstar

        set U := u.matches' with hU
        set U0 := u0.matches' with hU0d
        set U1 := u1.matches' with hU1d
        set D := (KStar.kstar U0) with hDd
        set C := U1 * D * U1 * D with hCd
        have hU0 : U0 ≤ U := fun w hw => ((mu0 w).1 hw).1
        have hU1 : U1 ≤ U := fun w hw => ((mu1 w).1 hw).1
        have hUsplit : U ≤ U0 + U1 := by
          intro w hw
          refine (Language.mem_add U0 U1 w).2 ?_
          rcases Nat.mod_two_eq_zero_or_one w.length with h | h
          · exact Or.inl ((mu0 w).2 ⟨hw, h⟩)
          · exact Or.inr ((mu1 w).2 ⟨hw, h⟩)
        have hD : D ≤ (KStar.kstar U) := kstar_mono hU0
        have hU1s : U1 ≤ (KStar.kstar U) := hU1.trans le_kstar
        have hC : C ≤ (KStar.kstar U) := by
          calc C ≤ (KStar.kstar U) * (KStar.kstar U) * (KStar.kstar U) * (KStar.kstar U) := by rw [hCd]; gcongr
            _ = (KStar.kstar U) := by rw [kstar_mul_kstar, kstar_mul_kstar, kstar_mul_kstar]
        have hCs : (KStar.kstar C) ≤ (KStar.kstar U) := by
          calc (KStar.kstar C) ≤ KStar.kstar (KStar.kstar U) := kstar_mono hC
            _ = (KStar.kstar U) := kstar_idem U
        have hA : D * (KStar.kstar C) ≤ (KStar.kstar U) := by
          calc D * (KStar.kstar C) ≤ (KStar.kstar U) * (KStar.kstar U) := by gcongr
            _ = (KStar.kstar U) := kstar_mul_kstar U
        have hB : D * U1 * D * (KStar.kstar C) ≤ (KStar.kstar U) := by
          calc D * U1 * D * (KStar.kstar C) ≤ (KStar.kstar U) * (KStar.kstar U) * (KStar.kstar U) * (KStar.kstar U) := by gcongr
            _ = (KStar.kstar U) := by rw [kstar_mul_kstar, kstar_mul_kstar, kstar_mul_kstar]
        have h1D : (1 : Language α) ≤ D := one_le_kstar
        have h1C : (1 : Language α) ≤ (KStar.kstar C) := one_le_kstar
  9. The language L(u)* is contained in the union of L(r₀) and L(r₁): U* ≤ D C* + D U₁ D C*.

    By the star induction rule `kstar_le_of_mul_le_right`, it suffices to show 1 ≤ X and U X ≤ X for X = D C* + D U₁ D C*. The unit inequality 1 ≤ X holds because 1 = 1 * 1 ≤ D C* ≤ X using `mul_one`, `add_eq_sup`, and `le_sup_left`. For U X ≤ X, since U ≤ U₀ + U₁, multiplying X on the left expands via distributivity (`add_mul`, `mul_add`, `mul_assoc`) into four terms: U₀ D C*, U₀ D U₁ D C*, U₁ D C*, and C C*. Using `mul_kstar_le_kstar` (giving U₀ D ≤ D and C C* ≤ C*) and `one_mul` (via 1 ≤ D), each term is bounded by D C* or D U₁ D C*. The sum of these four bounds simplifies to X using `sup_le`, `le_rfl`, `le_sup_left`, and `le_sup_right`.

    lines 154–179

    uses add_eq_sup, add_mul, kstar_le_of_mul_le_right, le_rfl, le_sup_left, le_sup_right, mul_add, mul_assoc, mul_kstar_le_kstar, mul_one, one_mul, sup_le

        have hAB : (KStar.kstar U) ≤ D * (KStar.kstar C) + D * U1 * D * (KStar.kstar C) := by
          apply kstar_le_of_mul_le_right
          · calc (1 : Language α) = 1 * 1 := (mul_one 1).symm
              _ ≤ D * (KStar.kstar C) := by gcongr
              _ ≤ _ := by rw [add_eq_sup]; exact le_sup_left
          · calc U * (D * (KStar.kstar C) + D * U1 * D * (KStar.kstar C)) ≤ (U0 + U1) * (D * (KStar.kstar C) + D * U1 * D * (KStar.kstar C)) := by
                  gcongr
              _ = U0 * D * (KStar.kstar C) + U0 * D * U1 * D * (KStar.kstar C) + (U1 * D * (KStar.kstar C) + C * (KStar.kstar C)) := by
                  rw [hCd]
                  simp only [add_mul, mul_add, mul_assoc]
                  abel
              _ ≤ D * (KStar.kstar C) + D * U1 * D * (KStar.kstar C) + (D * U1 * D * (KStar.kstar C) + D * (KStar.kstar C)) := by
                  have e1 : U0 * D ≤ D := mul_kstar_le_kstar
                  have e2 : U1 * D * (KStar.kstar C) ≤ D * U1 * D * (KStar.kstar C) := by
                    calc U1 * D * (KStar.kstar C) = 1 * U1 * D * (KStar.kstar C) := by rw [one_mul]
                      _ ≤ D * U1 * D * (KStar.kstar C) := by gcongr
                  have e3 : C * (KStar.kstar C) ≤ D * (KStar.kstar C) := by
                    calc C * (KStar.kstar C) ≤ (KStar.kstar C) := mul_kstar_le_kstar
                      _ = 1 * (KStar.kstar C) := (one_mul _).symm
                      _ ≤ D * (KStar.kstar C) := by gcongr
                  have e4 : U0 * D * U1 * D * (KStar.kstar C) ≤ D * U1 * D * (KStar.kstar C) := by gcongr
                  have e5 : U0 * D * (KStar.kstar C) ≤ D * (KStar.kstar C) := by gcongr
                  gcongr
              _ ≤ D * (KStar.kstar C) + D * U1 * D * (KStar.kstar C) := by
                  simp only [add_eq_sup]
                  exact sup_le le_rfl (sup_le le_sup_right le_sup_left)
  10. A word w matches r₀ if and only if w ∈ L(u)* and |w| is even, and matches r₁ if and only if w ∈ L(u)* and |w| is odd.

    For r₀: if w ∈ L(r₀) = D C*, it lies in U* by the direct inclusion and has even length by the parity invariant. Conversely, if w ∈ U* has even length, the reverse inclusion gives w ∈ D C* ∪ D U₁ D C* via `Language.mem_add`; if w belonged to D U₁ D C*, its length would be odd, a contradiction resolved by `omega`. The proof for r₁ is symmetric.

    lines 180–201

    uses Language.mem_add

        refine ⟨tA, tB, fun w => ?_, fun w => ?_⟩
        · change w ∈ D * (KStar.kstar C) ↔ w ∈ (KStar.kstar U) ∧ _
          constructor
          · intro hw
            exact ⟨hA hw, by simpa using toMod _ _ (pA w hw)⟩
          · rintro ⟨hw, hpar⟩
            rcases (Language.mem_add _ _ _).1 (hAB hw) with h | h
            · exact h
            · have := toMod _ _ (pB w h)
              rw [show (1 : ZMod 2).val = 1 from rfl] at this
              omega
        · change w ∈ D * U1 * D * (KStar.kstar C) ↔ w ∈ (KStar.kstar U) ∧ _
          constructor
          · intro hw
            exact ⟨hB hw, (toMod _ _ (pB w hw)).trans rfl⟩
          · rintro ⟨hw, hpar⟩
            rcases (Language.mem_add _ _ _).1 (hAB hw) with h | h
            · have := toMod _ _ (pA w h)
              simp at this
              omega
            · exact h
    
  11. Every regular expression r admits a parity normal form: there exist expressions r₀ and r₁ of typed parity 0 and 1 matching the even- and odd-length words of r.

    The existential witnesses are the two components of `regular_expression_parity_split r`, whose required properties are precisely those proven in `regular_expression_parity_split_spec`.

    lines 202–207

    uses regular_expression_parity_split_spec

    theorem regular_expression_exists_parity_normal_form {α : Type*} (r : RegularExpression α) :
        ∃ r₀ r₁ : RegularExpression α,
          regular_expression_typed_parity r₀ 0 ∧ regular_expression_typed_parity r₁ 1 ∧
          (∀ w, w ∈ r₀.matches' ↔ w ∈ r.matches' ∧ w.length % 2 = 0) ∧
          (∀ w, w ∈ r₁.matches' ↔ w ∈ r.matches' ∧ w.length % 2 = 1) :=
      ⟨_, _, regular_expression_parity_split_spec r⟩
add_mul
Multiplication distributes over addition on the right: (a + b) * c = a * c + b * c.
add_eq_sup
In an idempotent semiring, addition equals the least upper bound: a + b = a ⊔ b.
false_iff
The equivalence False ↔ p is equivalent to ¬p.
kstar_idem
The Kleene star operation is idempotent: (A*)* = A*.
kstar_le_of_mul_le_right
If 1 ≤ b and a * b ≤ b in a Kleene algebra, then a* ≤ b.
kstar_mono
The Kleene star operation is monotone with respect to language inclusion.
kstar_mul_kstar
Concatenating a Kleene star with itself is idempotent: A* * A* = A*.
Language.mem_add
A word belongs to the sum (union) of two languages if and only if it belongs to at least one of them.
Language.mem_mul
A word belongs to the product of two languages if and only if it can be split into two subwords belonging to the respective languages.
Language.mem_one
A word belongs to the unit language 1 if and only if it is the empty word.
Language.notMem_zero
No word belongs to the zero (empty) language.
le_kstar
Any language is contained in its Kleene star closure: a ≤ a*.
le_rfl
The order relation is reflexive: a ≤ a.
le_sup_left
Any element is bounded above by its join with another: a ≤ a ⊔ b.
le_sup_right
Any element is bounded above by the join of another with it: b ≤ a ⊔ b.
List.length_append
The length of the concatenation of two lists is the sum of their lengths.
mul_add
Multiplication distributes over addition on the left: a * (b + c) = a * b + a * c.
mul_assoc
Multiplication is associative: (a * b) * c = a * (b * c).
mul_kstar_le_kstar
In a Kleene algebra, a * a* ≤ a*.
mul_one
Multiplying an element by 1 on the right yields the element itself.
Nat.mod_two_eq_zero_or_one
Every natural number modulo 2 is either 0 or 1.
not_and
Negation of a conjunction ¬(a ∧ b) is equivalent to a → ¬b.
one_mul
Multiplying an element by 1 on the left yields the element itself.
one_le_kstar
The unit language 1 is contained in the Kleene star closure of any language.
Or.inl
Constructs a proof of a disjunction a ∨ b from a proof of the left disjunct a.
Or.inr
Constructs a proof of a disjunction a ∨ b from a proof of the right disjunct b.
regular_expression_parity_split
The recursive function splitting a regular expression into its even-length and odd-length components.
regular_expression_parity_split_spec
The components produced by `regular_expression_parity_split r` have typed parity 0 and 1, respectively, and match precisely the even-length and odd-length words of r.
regular_expression_typed_parity_length
If a regular expression has typed parity p, then every word matching it has length congruent to p modulo 2.
sup_le
If a ≤ c and b ≤ c, then a ⊔ b ≤ c.
ZMod.val_natCast
The canonical natural number value of the coercion of a natural number into ZMod n is its remainder modulo n.

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

def regular_expression_parity_split {α : Type*} :    RegularExpression α → RegularExpression α × RegularExpression α  | .zero => (0, 0)  | .epsilon => (1, 0)  | .char a => (0, .char a)  | .plus u v =>    ((regular_expression_parity_split u).1 + (regular_expression_parity_split v).1,      (regular_expression_parity_split u).2 + (regular_expression_parity_split v).2)  | .comp u v =>    ((regular_expression_parity_split u).1 * (regular_expression_parity_split v).1 +        (regular_expression_parity_split u).2 * (regular_expression_parity_split v).2,      (regular_expression_parity_split u).1 * (regular_expression_parity_split v).2 +        (regular_expression_parity_split u).2 * (regular_expression_parity_split v).1)  | .star u =>    (RegularExpression.star (regular_expression_parity_split u).1 *        RegularExpression.star ((regular_expression_parity_split u).2 *          RegularExpression.star (regular_expression_parity_split u).1 *          (regular_expression_parity_split u).2 *          RegularExpression.star (regular_expression_parity_split u).1),      RegularExpression.star (regular_expression_parity_split u).1 *        (regular_expression_parity_split u).2 *        RegularExpression.star (regular_expression_parity_split u).1 *        RegularExpression.star ((regular_expression_parity_split u).2 *          RegularExpression.star (regular_expression_parity_split u).1 *          (regular_expression_parity_split u).2 *          RegularExpression.star (regular_expression_parity_split u).1))theorem regular_expression_parity_split_spec {α : Type*} (r : RegularExpression α) :    regular_expression_typed_parity (regular_expression_parity_split r).1 0 ∧      regular_expression_typed_parity (regular_expression_parity_split r).2 1 ∧      (∀ w, w ∈ (regular_expression_parity_split r).1.matches' ↔        w ∈ r.matches' ∧ w.length % 2 = 0) ∧      (∀ w, w ∈ (regular_expression_parity_split r).2.matches' ↔        w ∈ r.matches' ∧ w.length % 2 = 1) := by  have h11 : (1 : ZMod 2) + 1 = 0 := by decide  induction r with  | zero =>    refine ⟨trivial, trivial, fun w => ?_, fun w => ?_⟩ <;>    · change w ∈ (0 : Language α) ↔ w ∈ (0 : Language α) ∧ _      simp [Language.notMem_zero]  | epsilon =>    refine ⟨rfl, trivial, fun w => ?_, fun w => ?_⟩    · change w ∈ (1 : Language α) ↔ w ∈ (1 : Language α) ∧ _      rw [Language.mem_one]      constructor      · rintro rfl; simp      · exact fun h => h.1    · change w ∈ (0 : Language α) ↔ w ∈ (1 : Language α) ∧ _      rw [Language.mem_one]      simp only [Language.notMem_zero, false_iff, not_and]      rintro rfl      simp  | char a =>    refine ⟨trivial, rfl, fun w => ?_, fun w => ?_⟩    · change w ∈ (0 : Language α) ↔ w ∈ ({[a]} : Language α) ∧ _      simp only [Language.notMem_zero, false_iff, not_and]      intro h      replace h : w = [a] := h      subst h      simp    · change w ∈ ({[a]} : Language α) ↔ w ∈ ({[a]} : Language α) ∧ _      constructor      · intro h        refine ⟨h, ?_⟩        replace h : w = [a] := h        subst h        simp      · exact fun h => h.1  | plus u v ihu ihv =>    obtain ⟨tu0, tu1, mu0, mu1⟩ := ihu    obtain ⟨tv0, tv1, mv0, mv1⟩ := ihv    refine ⟨⟨tu0, tv0⟩, ⟨tu1, tv1⟩, fun w => ?_, fun w => ?_⟩    · change w ∈ _ + _ ↔ w ∈ u.matches' + v.matches' ∧ _      rw [Language.mem_add, Language.mem_add, mu0, mv0]      tauto    · change w ∈ _ + _ ↔ w ∈ u.matches' + v.matches' ∧ _      rw [Language.mem_add, Language.mem_add, mu1, mv1]      tauto  | comp u v ihu ihv =>    obtain ⟨tu0, tu1, mu0, mu1⟩ := ihu    obtain ⟨tv0, tv1, mv0, mv1⟩ := ihv    refine ⟨⟨⟨0, 0, by decide, tu0, tv0⟩, ⟨1, 1, h11, tu1, tv1⟩⟩,      ⟨⟨0, 1, by decide, tu0, tv1⟩, ⟨1, 0, by decide, tu1, tv0⟩⟩, fun w => ?_, fun w => ?_⟩    · change w ∈ _ * _ + _ * _ ↔ w ∈ u.matches' * v.matches' ∧ _      simp only [Language.mem_add, Language.mem_mul, mu0, mu1, mv0, mv1]      constructor      · rintro (⟨a, ⟨ha, ha'⟩, b, ⟨hb, hb'⟩, rfl⟩ | ⟨a, ⟨ha, ha'⟩, b, ⟨hb, hb'⟩, rfl⟩) <;>        exact ⟨⟨a, ha, b, hb, rfl⟩, by simp [List.length_append]; omega⟩      · rintro ⟨⟨a, ha, b, hb, rfl⟩, hw⟩        rw [List.length_append] at hw        rcases Nat.mod_two_eq_zero_or_one a.length with h | h        · exact Or.inl ⟨a, ⟨ha, h⟩, b, ⟨hb, by omega⟩, rfl⟩        · exact Or.inr ⟨a, ⟨ha, h⟩, b, ⟨hb, by omega⟩, rfl⟩    · change w ∈ _ * _ + _ * _ ↔ w ∈ u.matches' * v.matches' ∧ _      simp only [Language.mem_add, Language.mem_mul, mu0, mu1, mv0, mv1]      constructor      · rintro (⟨a, ⟨ha, ha'⟩, b, ⟨hb, hb'⟩, rfl⟩ | ⟨a, ⟨ha, ha'⟩, b, ⟨hb, hb'⟩, rfl⟩) <;>        exact ⟨⟨a, ha, b, hb, rfl⟩, by simp [List.length_append]; omega⟩      · rintro ⟨⟨a, ha, b, hb, rfl⟩, hw⟩        rw [List.length_append] at hw        rcases Nat.mod_two_eq_zero_or_one a.length with h | h        · exact Or.inl ⟨a, ⟨ha, h⟩, b, ⟨hb, by omega⟩, rfl⟩        · exact Or.inr ⟨a, ⟨ha, h⟩, b, ⟨hb, by omega⟩, rfl⟩  | star u ihu =>    obtain ⟨tu0, tu1, mu0, mu1⟩ := ihu    simp only [regular_expression_parity_split]    set u0 := (regular_expression_parity_split u).1 with hu0    set u1 := (regular_expression_parity_split u).2 with hu1    have tc : regular_expression_typed_parity        (u1 * RegularExpression.star u0 * u1 * RegularExpression.star u0) 0 :=      ⟨0, 0, by decide, ⟨1, 1, h11, ⟨1, 0, by decide, tu1, ⟨rfl, tu0⟩⟩, tu1⟩, ⟨rfl, tu0⟩⟩    have tA : regular_expression_typed_parity (RegularExpression.star u0 *        RegularExpression.star (u1 * RegularExpression.star u0 * u1 *          RegularExpression.star u0)) 0 :=      ⟨0, 0, by decide, ⟨rfl, tu0⟩, ⟨rfl, tc⟩⟩    have tB : regular_expression_typed_parity (RegularExpression.star u0 * u1 *        RegularExpression.star u0 * RegularExpression.star (u1 * RegularExpression.star u0 * u1 *          RegularExpression.star u0)) 1 :=      ⟨1, 0, by decide, ⟨1, 0, by decide, ⟨0, 1, by decide, ⟨rfl, tu0⟩, tu1⟩, ⟨rfl, tu0⟩⟩,        ⟨rfl, tc⟩⟩    have pA := regular_expression_typed_parity_length _ 0 tA    have pB := regular_expression_typed_parity_length _ 1 tB    have toMod : ∀ (n : ℕ) (p : ZMod 2), (n : ZMod 2) = p → n % 2 = p.val := fun n p h => by      rw [← h, ZMod.val_natCast]    set U := u.matches' with hU    set U0 := u0.matches' with hU0d    set U1 := u1.matches' with hU1d    set D := (KStar.kstar U0) with hDd    set C := U1 * D * U1 * D with hCd    have hU0 : U0 ≤ U := fun w hw => ((mu0 w).1 hw).1    have hU1 : U1 ≤ U := fun w hw => ((mu1 w).1 hw).1    have hUsplit : U ≤ U0 + U1 := by      intro w hw      refine (Language.mem_add U0 U1 w).2 ?_      rcases Nat.mod_two_eq_zero_or_one w.length with h | h      · exact Or.inl ((mu0 w).2 ⟨hw, h⟩)      · exact Or.inr ((mu1 w).2 ⟨hw, h⟩)    have hD : D ≤ (KStar.kstar U) := kstar_mono hU0    have hU1s : U1 ≤ (KStar.kstar U) := hU1.trans le_kstar    have hC : C ≤ (KStar.kstar U) := by      calc C ≤ (KStar.kstar U) * (KStar.kstar U) * (KStar.kstar U) * (KStar.kstar U) := by rw [hCd]; gcongr        _ = (KStar.kstar U) := by rw [kstar_mul_kstar, kstar_mul_kstar, kstar_mul_kstar]    have hCs : (KStar.kstar C) ≤ (KStar.kstar U) := by      calc (KStar.kstar C) ≤ KStar.kstar (KStar.kstar U) := kstar_mono hC        _ = (KStar.kstar U) := kstar_idem U    have hA : D * (KStar.kstar C) ≤ (KStar.kstar U) := by      calc D * (KStar.kstar C) ≤ (KStar.kstar U) * (KStar.kstar U) := by gcongr        _ = (KStar.kstar U) := kstar_mul_kstar U    have hB : D * U1 * D * (KStar.kstar C) ≤ (KStar.kstar U) := by      calc D * U1 * D * (KStar.kstar C) ≤ (KStar.kstar U) * (KStar.kstar U) * (KStar.kstar U) * (KStar.kstar U) := by gcongr        _ = (KStar.kstar U) := by rw [kstar_mul_kstar, kstar_mul_kstar, kstar_mul_kstar]    have h1D : (1 : Language α) ≤ D := one_le_kstar    have h1C : (1 : Language α) ≤ (KStar.kstar C) := one_le_kstar    have hAB : (KStar.kstar U) ≤ D * (KStar.kstar C) + D * U1 * D * (KStar.kstar C) := by      apply kstar_le_of_mul_le_right      · calc (1 : Language α) = 1 * 1 := (mul_one 1).symm          _ ≤ D * (KStar.kstar C) := by gcongr          _ ≤ _ := by rw [add_eq_sup]; exact le_sup_left      · calc U * (D * (KStar.kstar C) + D * U1 * D * (KStar.kstar C)) ≤ (U0 + U1) * (D * (KStar.kstar C) + D * U1 * D * (KStar.kstar C)) := by              gcongr          _ = U0 * D * (KStar.kstar C) + U0 * D * U1 * D * (KStar.kstar C) + (U1 * D * (KStar.kstar C) + C * (KStar.kstar C)) := by              rw [hCd]              simp only [add_mul, mul_add, mul_assoc]              abel          _ ≤ D * (KStar.kstar C) + D * U1 * D * (KStar.kstar C) + (D * U1 * D * (KStar.kstar C) + D * (KStar.kstar C)) := by              have e1 : U0 * D ≤ D := mul_kstar_le_kstar              have e2 : U1 * D * (KStar.kstar C) ≤ D * U1 * D * (KStar.kstar C) := by                calc U1 * D * (KStar.kstar C) = 1 * U1 * D * (KStar.kstar C) := by rw [one_mul]                  _ ≤ D * U1 * D * (KStar.kstar C) := by gcongr              have e3 : C * (KStar.kstar C) ≤ D * (KStar.kstar C) := by                calc C * (KStar.kstar C) ≤ (KStar.kstar C) := mul_kstar_le_kstar                  _ = 1 * (KStar.kstar C) := (one_mul _).symm                  _ ≤ D * (KStar.kstar C) := by gcongr              have e4 : U0 * D * U1 * D * (KStar.kstar C) ≤ D * U1 * D * (KStar.kstar C) := by gcongr              have e5 : U0 * D * (KStar.kstar C) ≤ D * (KStar.kstar C) := by gcongr              gcongr          _ ≤ D * (KStar.kstar C) + D * U1 * D * (KStar.kstar C) := by              simp only [add_eq_sup]              exact sup_le le_rfl (sup_le le_sup_right le_sup_left)    refine ⟨tA, tB, fun w => ?_, fun w => ?_⟩    · change w ∈ D * (KStar.kstar C) ↔ w ∈ (KStar.kstar U) ∧ _      constructor      · intro hw        exact ⟨hA hw, by simpa using toMod _ _ (pA w hw)⟩      · rintro ⟨hw, hpar⟩        rcases (Language.mem_add _ _ _).1 (hAB hw) with h | h        · exact h        · have := toMod _ _ (pB w h)          rw [show (1 : ZMod 2).val = 1 from rfl] at this          omega    · change w ∈ D * U1 * D * (KStar.kstar C) ↔ w ∈ (KStar.kstar U) ∧ _      constructor      · intro hw        exact ⟨hB hw, (toMod _ _ (pB w hw)).trans rfl⟩      · rintro ⟨hw, hpar⟩        rcases (Language.mem_add _ _ _).1 (hAB hw) with h | h        · have := toMod _ _ (pA w h)          simp at this          omega        · exact htheorem regular_expression_exists_parity_normal_form {α : Type*} (r : RegularExpression α) :    ∃ r₀ r₁ : RegularExpression α,      regular_expression_typed_parity r₀ 0 ∧ regular_expression_typed_parity r₁ 1 ∧      (∀ w, w ∈ r₀.matches' ↔ w ∈ r.matches' ∧ w.length % 2 = 0) ∧      (∀ w, w ∈ r₁.matches' ↔ w ∈ r.matches' ∧ w.length % 2 = 1) :=  ⟨_, _, regular_expression_parity_split_spec r⟩
See it in the graphDiscuss this resultChallenge it