nfa_run_count_list_concat
Number of runs on w++[a] from p to q equals the sum over s of the number of runs on w from p to s, taken over the predecessors s of q on letter a.
Statement
open Classical in theorem nfa_run_count_list_concat {α σ : Type*} [Fintype σ] (M : NFA α σ) (w : List α) (a : α) (p q : σ) : nfa_run_count_list M (w ++ [a]) p q = ∑ s : σ, if q ∈ M.step s a then nfa_run_count_list M w p s else 0
- Source
- step towards pell_nfa_run_count_lower_bound
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- nfa_run_count_fiberwise_sumThe number of runs of w ++ [a] from p to q is the sum over all states s of the number of runs whose penultimate state is s.
- nfa_run_penultimate_fiberThe number of runs of w ++ [a] from p to q with penultimate state s equals the number of runs of w from p to s if q ∈ M.step s a, and 0…
- nfa_run_count_listThe number of runs of the word w in the NFA M from state p to state q: state sequences of length |w|+1 that start at p, end at q and…
- Used by 2
- 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_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.
The proof, explained
To count the runs on $w ++ [a]$ from state $p$ to state $q$, the proof fibers the runs according to their penultimate state $s$, which is the state visited after reading $w$ and immediately before reading $a$. Decomposing the count into a sum over all possible choices of $s$, each term reduces to the number of runs on $w$ from $p$ to $s$ if $q$ is an allowed successor of $s$ on input $a$, and zero otherwise.
The number of runs on $w ++ [a]$ from $p$ to $q$ is expressed as a sum over all states $s \in \sigma$ of the number of runs whose state at index $|w|$ (the penultimate state) is $s$.
Rewriting with `nfa_run_count_fiberwise_sum` partitions the set of runs of length $|w| + 1$ according to their value at index $|w|$, turning the single count into a fiberwise sum over each candidate penultimate state $s$.
uses
nfa_run_count_fiberwise_sumrw [nfa_run_count_fiberwise_sum]For each $s$, the size of the fiber is replaced by the number of runs on $w$ from $p$ to $s$ when $q \in M.\text{step}(s, a)$ and $0$ otherwise, matching the target sum.
Rewriting under the sum with `nfa_run_penultimate_fiber` simplifies each summand: a run on $w ++ [a]$ with penultimate state $s$ is uniquely determined by a run on $w$ ending at $s$, provided the final step from $s$ to $q$ on symbol $a$ is valid; if no such transition exists, the fiber is empty.
uses
nfa_run_penultimate_fibersimp_rw [nfa_run_penultimate_fiber]
nfa_run_count_fiberwise_sum- The total number of runs on the concatenated word $w ++ [a]$ from state $p$ to state $q$ equals the sum over all states $s$ of the number of runs whose penultimate state is $s$.
nfa_run_penultimate_fiber- The number of runs on $w ++ [a]$ from $p$ to $q$ with penultimate state $s$ equals the number of runs on $w$ from $p$ to $s$ if $q$ is reachable from $s$ on symbol $a$, and zero otherwise.
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.
open Classical in/-- Appending one letter distributes a run count over the possible previous state. -/theorem nfa_run_count_list_concat {α σ : Type*} [Fintype σ] (M : NFA α σ) (w : List α) (a : α) (p q : σ) : nfa_run_count_list M (w ++ [a]) p q = ∑ s : σ, if q ∈ M.step s a then nfa_run_count_list M w p s else 0 := by rw [nfa_run_count_fiberwise_sum] simp_rw [nfa_run_penultimate_fiber]