1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.