Determining Length of a walk in Nondeterministic Finite Automata with Lambda Transitions I am learning about CS Theory and specifically Nondeterministic Finite Automata (NFA) right now. In my book I came across a section of text that discussed a way to determine the length of a walk stating specifically that :


  If a transition graph has a walk labeled $w$, then there is a walk w of length no more than $\Lambda + (1 + \Lambda)|w|$ where $\Lambda$ is the number of $\lambda$ transitions in the graph.


The book does not define $|w|$ which is causing part of my confusion. I'm assuming $|w|$ is the length of the label of the walk. So in this case it would be 1 when going from $q_1 \to q_0 \to q1$ because $a$ is the only labeled edge.
I am trying to understand this concept and how it works because when I have tested out this claim it has not held true.

Here is the test I did with this NFA



$q_1$ is the final state. So assuming you were trying to find the length of the walk $a$, the label would indicate that the length is 1 (e.g. $\delta^* (q_1, a)$) . However due to the lambdas you actually have $\lambda \lambda a$ to go from $q_1 \to q_0 \to q_1$.

This theorem doesn't hold with my math though because it is defined as Λ + (1 + Λ)|w| where Λ is the number of λ-edges in the graph.

Since there are two λ-edges (and it doesn't state whether it means λ-edges in the walk itself or in the graph in total...) this would then be 2 + (1 + 2)|w|. So thats 2 + 3|w|. This clearly is more than 3, which is the length of q1 -> q1 of λλa.

What am I missing here? Any help is greatly appreciated.

This comes from Peter Linz "An Introduction to Formal Languages and Automata" 5th edition.

Some more information about the argument for this claim:


  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.


Also the book never names this as a theorem or lemma or anything of the sort so it has been very difficult to find online resources about this topic.
The length of the walk is the number of edges in the walk. Suppose $p$ is a walk labeled $w$. We can decompose $p$ into $p_1 e_1 p_2 e_2 \cdots p_{|w|} e_{|w|} p_{|w|+1}$, where each $p_i$ consists only of $\lambda$-transitions, and $e_i$ is a transition labeled $w_i$. There is always an equivalent walk in which no transition is taken twice in each $e_i$ (this is what is proved in the paragraph you quote), and so $|p_i| \leq \Lambda$. Therefore the entire walk has length at most $(1 + \Lambda) |w| + \Lambda$.