AFTD Auto-Formalizing Theoretical Domains

regular_expression_typed_parity_length

theoremverified

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

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.

  1. 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.

    lines 4–7

    uses Language.notMem_zero

      induction r generalizing p w with
      | zero =>
        change w ∈ (0 : Language α) at hw
        exact absurd hw (Language.notMem_zero w)
  2. 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).

    lines 8–12

    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.symm
  3. The 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).

    lines 13–16

      | char a =>
        replace hw : w = [a] := hw
        subst hw
        simpa [regular_expression_typed_parity] using hr.symm
  4. The 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).

    lines 17–22

    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 hw
  5. The 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).

    lines 23–28

    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]
  6. 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).

    lines 29–33

    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]
  7. 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).

    lines 34–35

        induction L with
        | nil => simp
  8. 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).

    lines 36–39

    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

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]
See it in the graphDiscuss this resultChallenge it