AFTD Auto-Formalizing Theoretical Domains

pell_nfa_is_trim

theoremverified

The n-state Pell NFA pell_nfa n is trim: every state is reachable from the start state and can reach an accept state.

Statement

theorem pell_nfa_is_trim (n : ℕ) (hn : 3 ≤ n) : nfa_is_trim (pell_nfa n)
Source
step towards finitely_ambiguous_nfa_pell_lower_bound
Verified
19 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • pell_nfaFor every n, the 5-letter automaton A_n of the paper's lower bound: a chain q_1,…,q_n in which, for each 1 ≤ i ≤ n-2, the letter c_i…
  • nfa_is_trimAn NFA M is trim if every state q is reachable from the start states by some word and co-reachable (can reach an accept state by some word).

The proof, explained

To show that the Pell NFA with n ≥ 3 states is trim, we show that every state q is reachable from the initial state 0 and can reach the unique accept state n - 1. We establish this by constructing a directed path along the linear chain 0 → 1 → ... → n - 1. A helper lemma shows that from any state p < n - 1, a single step along the chain to p + 1 is valid under a designated input letter (letter 2 when p = 0, and p % 5 when p > 0). By induction on the distance m, any state p + m is reachable from state p by walking this chain. Setting p = 0 gives reachability from the start state to q, and setting p = q gives reachability from q to the accept state n - 1.

  1. The stepping letter from state p is well-defined as an element of Fin 5: it is 2 when p = 0, and p % 5 when p > 0.

    When p > 0, the remainder p % 5 is strictly less than 5 by Nat.mod_lt, since 0 < 5 is verified by numerical computation (norm_num).

    lines 1–3

    uses Nat.mod_lt

    /-- The letter of the `p`-th chain step: `2` from the first state, `p % 5` above. -/
    def pell_nfa_is_trim_letter (p : ℕ) : Fin 5 := if p = 0 then 2 else ⟨p % 5, Nat.mod_lt p (by norm_num)⟩
    
  2. A single chain step from p to p + 1 reduces to finding an index i that satisfies the Pell NFA transition relation.

    We fix states s and q with values p and p + 1. Unfolding the definition of pell_nfa, pell_nfa_is_trim_letter, and set comprehension membership via Set.mem_ofPred_eq, and substituting the values of s and q, the goal is to find an index i such that 1 ≤ i and i + 2 ≤ n satisfying the transition formula.

    lines 6–11

    uses pell_nfa, pell_nfa_is_trim_letter, Set.mem_ofPred_eq

    theorem pell_nfa_is_trim_step_succ (n p : ℕ) (hn : 3 ≤ n) (hp : p + 1 < n) :
        ∀ (s q : Fin n), s.val = p → q.val = p + 1 →
          q ∈ (pell_nfa n).step s (pell_nfa_is_trim_letter p) := by
      intro s q hs hq
      simp only [pell_nfa, pell_nfa_is_trim_letter, Set.mem_ofPred_eq]
      rw [hs, hq]
  3. For p = 0, state 0 transitions to state 1 with letter 2.

    We split on whether p = 0. When p = 0, the stepping letter is 2. Choosing index i = 1, the bounds 1 ≤ 1 and 1 + 2 ≤ n hold since n ≥ 3, and numerical evaluation (norm_num) verifies the second clause with (1 + 1) % 5 = 2, transitioning from 0 = i - 1 to 1 = i.

    lines 12–15

      by_cases hp0 : p = 0
      · rw [hp0]
        refine ⟨1, by norm_num, by omega, ?_⟩
        norm_num
  4. For p > 0, state p transitions to state p + 1 with letter p % 5.

    When p ≠ 0, we choose index i = p. Since p ≥ 1 and p + 1 < n, we have 1 ≤ p and p + 2 ≤ n. Simplifying with if_neg hp0 reduces the letter to p % 5 = i % 5, which satisfies the first transition clause from p = i to p + 1 = i + 1.

    lines 16–20

    uses if_neg

      · refine ⟨p, by omega, by omega, ?_⟩
        simp only [if_neg hp0]
        simp
    
    /-- From a state of value `p` one reaches any state of value `p + m` by walking the chain. -/
  5. Any state q of value p + m is reachable from state s of value p; in the base case m = 0, the empty word suffices.

    We induct on m. In the base case m = 0, the values of q and s are both p, so q = s by Fin.ext. Running the empty word [] from {s} keeps the automaton in {s} by NFA.evalFrom_nil and Set.mem_singleton_iff, reaching q.

    lines 21–28

    uses NFA.evalFrom_nil, Set.mem_singleton_iff, Fin.ext

    theorem pell_nfa_is_trim_reach_fwd (n : ℕ) (hn : 3 ≤ n) : ∀ (m p : ℕ), p + m < n →
        ∀ (s q : Fin n), s.val = p → q.val = p + m →
          ∃ w, q ∈ (pell_nfa n).evalFrom {s} w := by
      intro m
      induction m with
      | zero =>
        intro p hp s q hs hq
        exact ⟨[], by simp only [NFA.evalFrom_nil, Set.mem_singleton_iff]; exact Fin.ext (by omega)⟩
  6. In the induction step, extending a path of length m by one chain step reaches state q of value p + m + 1.

    By the induction hypothesis, there is a word w reaching the state with value p + m from s. By pell_nfa_is_trim_step_succ, reading pell_nfa_is_trim_letter (p + m) transitions from value p + m to state q with value p + m + 1. Appending this letter to w and rewriting via NFA.evalFrom_append, NFA.evalFrom_singleton, and NFA.mem_stepSet confirms that q is reached.

    lines 29–40

    uses pell_nfa_is_trim_step_succ, pell_nfa_is_trim_letter, NFA.evalFrom_append, NFA.evalFrom_singleton, NFA.mem_stepSet

      | succ m ih =>
        intro p hp s q hs hq
        have hpm : p + m < n := by omega
        obtain ⟨w, hw⟩ := ih p hpm s ⟨p + m, hpm⟩ hs rfl
        have hstep : q ∈ (pell_nfa n).step ⟨p + m, hpm⟩ (pell_nfa_is_trim_letter (p + m)) := by
          refine pell_nfa_is_trim_step_succ n (p + m) hn (by omega) _ q rfl ?_
          show (↑q : ℕ) = p + m + 1
          omega
        refine ⟨w ++ [pell_nfa_is_trim_letter (p + m)], ?_⟩
        simp only [NFA.evalFrom_append, NFA.evalFrom_singleton, NFA.mem_stepSet]
        exact ⟨_, hw, hstep⟩
    
  7. Every state q in the Pell NFA is reachable from the start state.

    Applying pell_nfa_is_trim_reach_fwd with start value 0 and distance q.val yields a word w reaching q from state 0. Since state 0 is the start state of pell_nfa n, NFA.mem_evalFrom_iff_exists.mpr shows that q is reachable from the NFA's start set.

    lines 41–46

    uses pell_nfa_is_trim_reach_fwd, NFA.mem_evalFrom_iff_exists.mpr

    /-- The n-state Pell NFA pell_nfa n is trim for n ≥ 3. -/
    theorem pell_nfa_is_trim (n : ℕ) (hn : 3 ≤ n) : nfa_is_trim (pell_nfa n) := by
      intro q
      constructor
      · obtain ⟨w, hw⟩ := pell_nfa_is_trim_reach_fwd n hn q.val 0 (by omega) ⟨0, by omega⟩ q rfl (by omega)
        exact ⟨w, NFA.mem_evalFrom_iff_exists.mpr ⟨⟨0, by omega⟩, rfl, hw⟩⟩
  8. Every state q in the Pell NFA can reach an accept state, completing the proof that the NFA is trim.

    The accept condition in pell_nfa n is val + 1 = n, which corresponds uniquely to state n - 1. Applying pell_nfa_is_trim_reach_fwd from q with distance n - 1 - q.val yields a word w reaching state n - 1 from q. Since (n - 1) + 1 = n, state n - 1 is an accept state, proving that pell_nfa n is trim.

    lines 47–49

    uses pell_nfa_is_trim_reach_fwd

      · obtain ⟨w, hw⟩ := pell_nfa_is_trim_reach_fwd n hn (n - 1 - q.val) q.val (by omega) q
          ⟨n - 1, by omega⟩ rfl (by simp; omega)
        exact ⟨w, ⟨n - 1, by omega⟩, by show (n - 1) + 1 = n; omega, hw⟩
Nat.mod_lt
For any natural numbers x and y with y > 0, the remainder x % y satisfies x % y < y.
pell_nfa
The definition of the Pell NFA on n states with alphabet Fin 5, having start state 0, accept state n - 1, and transition relation defined by modular arithmetic conditions.
pell_nfa_is_trim_letter
The stepping letter for state value p, defined as 2 if p = 0, and p % 5 (in Fin 5) if p > 0.
Set.mem_ofPred_eq
Membership of an element x in a set defined by a predicate {y | p y} is definitionally equivalent to p x.
if_neg
If a proposition c is false, then the conditional expression if c then t else e evaluates to e.
NFA.evalFrom_nil
Evaluating an NFA on the empty word [] from a state set S leaves the set S unchanged.
Set.mem_singleton_iff
An element a belongs to the singleton set {b} if and only if a = b.
Fin.ext
Two elements of Fin n are equal if and only if their underlying natural number values are equal.
pell_nfa_is_trim_step_succ
In the Pell NFA with n ≥ 3 states, if p + 1 < n, then reading letter pell_nfa_is_trim_letter p transitions from any state with value p to any state with value p + 1.
NFA.evalFrom_append
Evaluating an NFA on a concatenated word x ++ y from state set S equals evaluating on y starting from the set of states reached after reading x.
NFA.evalFrom_singleton
Evaluating an NFA on a single-letter word [a] from state set S equals the one-step set transition stepSet S a.
NFA.mem_stepSet
A state s belongs to stepSet S a if and only if s is reachable in one step on letter a from some state t in S.
pell_nfa_is_trim_reach_fwd
In the Pell NFA with n ≥ 3 states, for any p and m with p + m < n, any state of value p + m is reachable by some word starting from any state of value p.
NFA.mem_evalFrom_iff_exists.mpr
If a state is reachable on word w from the singleton {t} for some t in S, then it is reachable on word w from the set of states S.

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

/-- The letter of the `p`-th chain step: `2` from the first state, `p % 5` above. -/def pell_nfa_is_trim_letter (p : ℕ) : Fin 5 := if p = 0 then 2 else ⟨p % 5, Nat.mod_lt p (by norm_num)⟩/-- A single chain step: from a state of value `p` the letter `pell_nfa_is_trim_letter p` reaches anystate of value `p + 1`. -/theorem pell_nfa_is_trim_step_succ (n p : ℕ) (hn : 3 ≤ n) (hp : p + 1 < n) :    ∀ (s q : Fin n), s.val = p → q.val = p + 1 →      q ∈ (pell_nfa n).step s (pell_nfa_is_trim_letter p) := by  intro s q hs hq  simp only [pell_nfa, pell_nfa_is_trim_letter, Set.mem_ofPred_eq]  rw [hs, hq]  by_cases hp0 : p = 0  · rw [hp0]    refine ⟨1, by norm_num, by omega, ?_⟩    norm_num  · refine ⟨p, by omega, by omega, ?_⟩    simp only [if_neg hp0]    simp/-- From a state of value `p` one reaches any state of value `p + m` by walking the chain. -/theorem pell_nfa_is_trim_reach_fwd (n : ℕ) (hn : 3 ≤ n) : ∀ (m p : ℕ), p + m < n →    ∀ (s q : Fin n), s.val = p → q.val = p + m →      ∃ w, q ∈ (pell_nfa n).evalFrom {s} w := by  intro m  induction m with  | zero =>    intro p hp s q hs hq    exact ⟨[], by simp only [NFA.evalFrom_nil, Set.mem_singleton_iff]; exact Fin.ext (by omega)⟩  | succ m ih =>    intro p hp s q hs hq    have hpm : p + m < n := by omega    obtain ⟨w, hw⟩ := ih p hpm s ⟨p + m, hpm⟩ hs rfl    have hstep : q ∈ (pell_nfa n).step ⟨p + m, hpm⟩ (pell_nfa_is_trim_letter (p + m)) := by      refine pell_nfa_is_trim_step_succ n (p + m) hn (by omega) _ q rfl ?_      show (↑q : ℕ) = p + m + 1      omega    refine ⟨w ++ [pell_nfa_is_trim_letter (p + m)], ?_⟩    simp only [NFA.evalFrom_append, NFA.evalFrom_singleton, NFA.mem_stepSet]    exact ⟨_, hw, hstep⟩/-- The n-state Pell NFA pell_nfa n is trim for n ≥ 3. -/theorem pell_nfa_is_trim (n : ℕ) (hn : 3 ≤ n) : nfa_is_trim (pell_nfa n) := by  intro q  constructor  · obtain ⟨w, hw⟩ := pell_nfa_is_trim_reach_fwd n hn q.val 0 (by omega) ⟨0, by omega⟩ q rfl (by omega)    exact ⟨w, NFA.mem_evalFrom_iff_exists.mpr ⟨⟨0, by omega⟩, rfl, hw⟩⟩  · obtain ⟨w, hw⟩ := pell_nfa_is_trim_reach_fwd n hn (n - 1 - q.val) q.val (by omega) q      ⟨n - 1, by omega⟩ rfl (by simp; omega)    exact ⟨w, ⟨n - 1, by omega⟩, by show (n - 1) + 1 = n; omega, hw⟩
See it in the graphDiscuss this resultChallenge it