regular_expression_exists_parity_normal_form
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
- regular_expression_typed_parityA regular expression is typed with parity p ∈ ℤ/2 by the rules: ∅ may be given either parity, ε has parity 0, every letter has parity 1, a…
- regular_expression_typed_parity_lengthEvery word in the language of an expression typed with parity p has length ≡ p (mod 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`.
In the ring ℤ/2ℤ, 1 + 1 = 0.
Established by the decision procedure `decide`, which evaluates 1 + 1 = 0 in the two-element ring ℤ/2ℤ.
have h11 : (1 : ZMod 2) + 1 = 0 := by decide
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.
uses
Language.notMem_zeroinduction r with | zero => refine ⟨trivial, trivial, fun w => ?_, fun w => ?_⟩ <;> · change w ∈ (0 : Language α) ↔ w ∈ (0 : Language α) ∧ _ simp [Language.notMem_zero]
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`.
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 simpThe 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).
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.1The 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`).
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] tautoThe 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.
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⟩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.
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]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`.
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_kstarset 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
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`.
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_lehave 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)
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.
uses
Language.mem_addrefine ⟨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
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`.
uses
regular_expression_parity_split_spectheorem 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.
- In the Kleene star case, the reverse inclusion L(u)* ⊆ L(r₀) ∪ L(r₁) is established by applying the right Kleene algebra star induction rule `kstar_le_of_mul_le_right` to an idempotent semiring of formal languages.
- The arithmetic solver `omega` is used to discharge several parity and length modular arithmetic goals across the concatenation and star cases.
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.
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⟩