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.
Determining Length of a walk in Nondeterministic Finite Automata with Lambda Transitions
graph theory;finite automata;nondeterminism