regular_expression_typed_parity_length
Every word in the language of an expression typed with parity p has length ≡ p (mod 2).
Statement
theorem regular_expression_typed_parity_length {α : Type*} (r : RegularExpression α) (p : ZMod 2) (hr : regular_expression_typed_parity r p) (w : List α) (hw : w ∈ r.matches') : (w.length : ZMod 2) = p
- Source
- Sanity lemma for regular_expression_typed_parity: the "immediate induction" remark after the typing rules in arXiv:2610.11717 (Every Regular Language Has a Bipartite Cactus Automaton), Sec. 3.1.
- Verified
- 12 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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…
- Used by 1
- regular_expression_exists_parity_normal_formFor every regular expression r there are regular expressions r₀ and r₁, typed with parity 0 and 1 respectively, with L(r₀) = {w ∈ L(r) :…
The proof, explained
The theorem is proved by structural induction on the regular expression r. The base cases (empty language, empty word, and single character) hold directly from their definitionally specified lengths and parities. Alternation decomposes into the two branches with the same parity, while concatenation decomposes the word into two subwords whose lengths sum to the required parity modulo 2. For the Kleene star, the typing guarantees parity 0, and an inner induction on the list of constituent words shows that concatenating words of even length yields an even length.
The base case r = 0 holds vacuously.
We proceed by structural induction on the regular expression r, generalizing over the parity p and the word w. In the base case where r is the empty expression 0, its language is empty. Because no word belongs to 0 (Language.notMem_zero), the assumption that w matches 0 is contradictory, closing this case vacuously.
uses
Language.notMem_zeroinduction r generalizing p w with | zero => change w ∈ (0 : Language α) at hw exact absurd hw (Language.notMem_zero w)
The base case r = ε holds: any matching word has length 0 ≡ p (mod 2).
The language of ε contains only the empty word [] (Language.mem_one), so w = []. Its length is 0. By the definition of regular_expression_typed_parity, the expression ε has parity p if and only if p = 0. Hence |w| ≡ 0 = p (mod 2).
uses
Language.mem_one| epsilon => change w ∈ (1 : Language α) at hw rw [Language.mem_one] at hw subst hw simpa [regular_expression_typed_parity] using hr.symmThe base case r = char(a) holds: any matching word has length 1 ≡ p (mod 2).
The only word matching a single character a is the singleton list [a], which has length 1. By definition, a character expression has parity p if and only if p = 1. Thus |w| ≡ 1 = p (mod 2).
| char a => replace hw : w = [a] := hw subst hw simpa [regular_expression_typed_parity] using hr.symmThe inductive step for alternation r + s holds.
A word w belongs to the language of r + s if and only if it belongs to the language of r or to the language of s (Language.mem_add). The parity typing for r + s requires both r and s to have parity p. Case splitting on which branch w belongs to, the induction hypothesis for that branch immediately gives |w| ≡ p (mod 2).
uses
Language.mem_add| plus r s ihr ihs => change w ∈ r.matches' + s.matches' at hw rw [Language.mem_add] at hw rcases hw with hw | hw · exact ihr p hr.1 w hw · exact ihs p hr.2 w hwThe inductive step for concatenation r · s holds.
A word w belongs to the concatenation r · s if and only if w = a ++ b with a matching r and b matching s (Language.mem_mul). The typing condition for concatenation provides parities q₁, q₂ ∈ ℤ/2ℤ such that q₁ + q₂ = p, with r typed with parity q₁ and s typed with parity q₂. The length of an appended list is the sum of the lengths (List.length_append), which translates under the coercion to ℤ/2ℤ to addition (Nat.cast_add). Applying the induction hypotheses to a and b yields |w| ≡ |a| + |b| ≡ q₁ + q₂ = p (mod 2).
uses
Language.mem_mul,List.length_append,Nat.cast_add| comp r s ihr ihs => change w ∈ r.matches' * s.matches' at hw rw [Language.mem_mul] at hw obtain ⟨a, ha, b, hb, rfl⟩ := hw obtain ⟨q₁, q₂, hq, h₁, h₂⟩ := hr rw [List.length_append, Nat.cast_add, ihr q₁ h₁ a ha, ihs q₂ h₂ b hb, hq]For the Kleene star r*, the word decomposes into a list of matches of r, reducing the goal to showing that the flattened length is 0 (mod 2).
A word w belongs to the Kleene star r* if and only if w is the flattening of a list of words L, each belonging to the language of r (Language.mem_kstar). The typing assumption for r* requires that p = 0 and that r has parity 0. Rewriting p to 0 reduces the goal to proving that |L.flatten| ≡ 0 (mod 2).
uses
Language.mem_kstar| star r ihr => change w ∈ KStar.kstar r.matches' at hw rw [Language.mem_kstar] at hw obtain ⟨L, rfl, hL⟩ := hw rw [hr.1]The base case L = [] of the flattened list has length 0 (mod 2).
We proceed by induction on the list of words L. For the empty list L = [], the flattened list is [] with length 0, which trivially satisfies |[].flatten| ≡ 0 (mod 2).
induction L with | nil => simp
The inductive step for y :: L preserves parity 0 (mod 2).
For a non-empty list y :: L, the flattened list is y ++ L.flatten (List.flatten_cons). Its length modulo 2 is |y| + |L.flatten| by List.length_append and Nat.cast_add. Since y is the head of y :: L (List.mem_cons_self), y matches r, so the outer induction hypothesis on r with parity 0 gives |y| ≡ 0 (mod 2). Every element in L also matches r (List.mem_cons_of_mem), so the inner induction hypothesis gives |L.flatten| ≡ 0 (mod 2). By add_zero, the sum simplifies to 0 + 0 = 0 (mod 2).
uses
List.flatten_cons,List.length_append,Nat.cast_add,List.mem_cons_self,List.mem_cons_of_mem,add_zero| cons y L ih => rw [List.flatten_cons, List.length_append, Nat.cast_add, ihr 0 hr.2 y (hL y (List.mem_cons_self ..)), ih (fun z hz => hL z (List.mem_cons_of_mem _ hz)), add_zero]
Language.notMem_zero- The empty language 0 contains no words.
Language.mem_one- A word belongs to the language 1 if and only if it is the empty word.
Language.mem_add- A word belongs to the union of two languages l + m if and only if it belongs to l or to m.
Language.mem_mul- A word belongs to the concatenation of languages l * m if and only if it can be decomposed into a word in l followed by a word in m.
List.length_append- The length of the concatenation of two lists is the sum of their lengths.
Nat.cast_add- The canonical coercion from natural numbers to an additive monoid with one preserves addition.
Language.mem_kstar- A word belongs to the Kleene star of a language l if and only if it is the concatenation (flattening) of a list of words, all of which belong to l.
List.flatten_cons- Flattening a list with head l and tail L yields the concatenation of l with the flattening of L.
List.mem_cons_self- The head element of a non-empty list belongs to that list.
List.mem_cons_of_mem- An element belonging to a list also belongs to the list obtained by prepending any element.
add_zero- Adding zero to an element leaves it unchanged.
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.
theorem regular_expression_typed_parity_length {α : Type*} (r : RegularExpression α) (p : ZMod 2) (hr : regular_expression_typed_parity r p) (w : List α) (hw : w ∈ r.matches') : (w.length : ZMod 2) = p := by induction r generalizing p w with | zero => change w ∈ (0 : Language α) at hw exact absurd hw (Language.notMem_zero w) | epsilon => change w ∈ (1 : Language α) at hw rw [Language.mem_one] at hw subst hw simpa [regular_expression_typed_parity] using hr.symm | char a => replace hw : w = [a] := hw subst hw simpa [regular_expression_typed_parity] using hr.symm | plus r s ihr ihs => change w ∈ r.matches' + s.matches' at hw rw [Language.mem_add] at hw rcases hw with hw | hw · exact ihr p hr.1 w hw · exact ihs p hr.2 w hw | comp r s ihr ihs => change w ∈ r.matches' * s.matches' at hw rw [Language.mem_mul] at hw obtain ⟨a, ha, b, hb, rfl⟩ := hw obtain ⟨q₁, q₂, hq, h₁, h₂⟩ := hr rw [List.length_append, Nat.cast_add, ihr q₁ h₁ a ha, ihs q₂ h₂ b hb, hq] | star r ihr => change w ∈ KStar.kstar r.matches' at hw rw [Language.mem_kstar] at hw obtain ⟨L, rfl, hL⟩ := hw rw [hr.1] induction L with | nil => simp | cons y L ih => rw [List.flatten_cons, List.length_append, Nat.cast_add, ihr 0 hr.2 y (hL y (List.mem_cons_self ..)), ih (fun z hz => hL z (List.mem_cons_of_mem _ hz)), add_zero]