Cycles in paths of certain length in an NFA

Question

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?

Answer 1

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.