For NFA(nondeterministic finite accepter), how long can a walk labeled string w be?
For example, the following graph has 4 length from $q_1$ to $q_2$ for string $a$(string consisting of only one alphabet symbol 'a').
There is an argument that
If between two vertices $v_i$ and $v_j$ there is any walk labeled $w$, then there must be some walk labeled $w$ of length no more than $Λ + (1 + Λ)|w|$, where $Λ$ is the number of $λ$-edges in the graph.
How to prove the argument? The following explanation is briefly written, but I don't understand it. How does it come out like that?
The argument for this is: While $λ$-edges may be repeated, there is always a walk in which every repeated $λ$-edge is separated by an edge labeled with a nonempty symbol. Otherwise, the walk contains a cycle labeled $λ$, which can be replaced by a simple path without changing the label of the walk.
Definitions and info:
- A sequence of edges $(v_i,v_j),(v_j,v_k),... ,(v_m,v_n)$ is said to be a walk from $v_i$ to $v_n$.
- A walk from $v_i$ to itself with no repeated edges is called a cycle with base $v_i$.
- The $λ$-transitions lengthen the walk but do not contribute to the label.
- The $|w|$ denotes the length of the string $w$.
UPDATE:
From what I understand, the case where the length of the path from $q_0$ to $q_1$ to create a specific string $ab$ is close to the maximum length defined by $Λ+(1+Λ)||$ would be as follows:
That is, the path is $λλλλλλaλλλλλλbλλλλλλ$.
I agree with the paragraph starting by "The argument for this".
Consider a path $p$ of minimal length labeled $w$. This path does not contain any cycle labeled $\lambda$ (otherwise you would obtain a shorter path with the same label $w$ by deleting this cycle). If some edge $q \xrightarrow{\lambda} q'$ occurs twice in $p$, then there is also a subpath of $p$ going from $q'$ to $q$. This subpath cannot be labeled $\lambda$, since otherwise you would have a cycle labeled $\lambda$ inside $p$.
I also agree with the bound $\Lambda + (1 + \Lambda)|w|$. Indeed if $w = a_1 \dotsm a_n$, with $n = |w|$, the path $p$ is of the form $$ q_0 \stackrel{p_0}{\leadsto} q_1 \xrightarrow{a_1} q'_1 \stackrel{p_1}{\leadsto} q_2 \xrightarrow{a_2} q'_2 \stackrel{p_2} {\leadsto} \ \dotsm \ q_n \xrightarrow{a_n} q'_n \stackrel{p_n} {\leadsto} q_{n+1} $$ where $p_0, p_1, \ldots, p_n$ are cycle-free paths labeled $\lambda$, and hence of length bounded by $\Lambda$. Thus the length of $p$ is bounded by $\Lambda + (1 + \Lambda)|w|$.