# Cycles in paths of certain length in an NFA

I saw this result used in a paper, but wasn't able to find a proof or reference for it:

Given an NFA with $$n$$ states and two paths $$i\xrightarrow{u}q$$ and $$i\xrightarrow{u}q'$$, with $$|u|>n^2$$, one can factorize the paths into

$$i\xrightarrow{u_1}p\xrightarrow{u_2}p\xrightarrow{u_3}q$$ and $$i\xrightarrow{u_1}p'\xrightarrow{u_2}p'\xrightarrow{u_3}q'$$

with $$u=u_1u_2u_3$$ and $$|u_2|>0$$.

I understand that each path has more than $$(n-1)n=n^2-n$$ cycles, but why must both have a cycle such that the inputs are the same?

Let $$u = a_1a_2 \dotsm a_m$$, where the $$a_i$$'s are letters. Let us spell the two paths as follows: \begin{align} &q_0 \xrightarrow{a_1} q_1 \xrightarrow{a_2} q_2 \quad \dotsm \quad \xrightarrow{a_m} q_m\\ &q_0 \xrightarrow{a_1} q'_1 \xrightarrow{a_2} q'_2 \quad \dotsm \quad \xrightarrow{a_m} q'_m \end{align} Since $$m > n^2$$, two of the pairs $$(q_i, q'_i)$$ are equal, say $$(q_i, q'_i) = (q_j, q'_j) = (p, p')$$. Setting $$u_1 = a_1 \dotsm a_i$$, $$u_2 = a_{i+1} \dots a_j$$ and $$u_3 = a_{j+1} \dotsm a_m$$ now gives the required factorization.