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.