AFTD Auto-Formalizing Theoretical Domains

pell_nfa

def

For 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 (subscripts mod 5) labels the transitions q_i→q_i, q_{i+1}→q_{i+1}, q_i→q_{i+2}, q_{i+1}→q_{i+2}, and the letter c_{i+1} labels q_{i+1}→q_{i+1}, q_{i+2}→q_{i+2}, q_i→q_{i+1}, q_i→q_{i+2}; the initial state is q_1 and the final state is q_n.

Statement

def pell_nfa (n : ℕ) : NFA (Fin 5) (Fin n)
Source
step towards finitely_ambiguous_nfa_pell_lower_bound
Verified
19 Oct 2026
Axioms
none listed
Used by 9
  • pell_nfa_no_idaThe Pell automaton A_n does not comply with IDA: there are no distinct states p, q and no word v such that p is reachable from p by v, q…
  • pell_run_encard_eq_countThe set of accepting runs of u_n in A_n has encard equal to the number of runs from q_1 to q_n.
  • pell_prefix_first_letter_vectorAfter appending only the letter c_(i+1) to the prefix, the run counts are P(i+1)-P(i) at q_i, 2P(i) at q_(i+1), (P(i+1)-P(i))+2P(i) at…
  • pell_run_level_le_start_add_twoIn the Pell automaton A_n, if a run starting at state p reads only letters congruent to c_p or to c_{p+1} (mod 5), then at every time its…
  • pell_prefix_base_countThe prefix c_1c_2 has 1 run from q_1 to q_2, 2 runs from q_1 to q_3, 1 run from q_1 to q_4, and no runs to any other state, in A_n.
  • pell_step_iffClosed form of the transitions of A_n: q is reachable from p in one step on letter k iff one of five explicit arithmetic conditions holds…
  • pell_nfa_has_singleton_sccsFor every natural number n, the n-state Pell NFA pell_nfa n has singleton strongly connected components.
  • pell_nfa_is_trimThe n-state Pell NFA pell_nfa n is trim: every state is reachable from the start state and can reach an accept state.
  • pell_nfa_step_tableIn A_n, if q is reachable from p in one step on letter k, then one of the following holds: (i) k ≡ p (mod 5) and q = p or q = p+1; (ii) k…

Lean source view module on GitHub

/-- The n-state five-letter NFA of the lower bound: a union of overlapping three-state gadgets, state ⟨j⟩ being q_(j+1) and letter ⟨i⟩ being c_i. -/
def pell_nfa (n : ℕ) : NFA (Fin 5) (Fin n) where
  step := fun p k => {q | ∃ i : ℕ, 1 ≤ i ∧ i + 2 ≤ n ∧
    ((k.val = i % 5 ∧
        ((p.val = i - 1 ∧ (q.val = i - 1 ∨ q.val = i + 1)) ∨
         (p.val = i ∧ (q.val = i ∨ q.val = i + 1)))) ∨
     (k.val = (i + 1) % 5 ∧
        ((p.val = i ∧ q.val = i) ∨ (p.val = i + 1 ∧ q.val = i + 1) ∨
         (p.val = i - 1 ∧ (q.val = i ∨ q.val = i + 1))))) }
  start := {p | p.val = 0}
  accept := {q | q.val + 1 = n}
See it in the graphDiscuss this resultChallenge it