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

enter image description here

$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.

  • 1
    $\begingroup$ $|w|$ is the length of the input word being read. So I don't see the problem. In your example of accepting the string "a", you have an accepting path of length 2, while the theorem says the length is not more than 5. Two isn't more than five so we're happy, aren't we? $\endgroup$ – David Richerby Nov 4 '13 at 21:06
  • $\begingroup$ @David Richerby Yes. I just figured this out for myself but what my book was defining was the maximum length of a walk in a graph from and vertice to any vertice. Ill edit soon when I get back home as to a more formal proof of this. $\endgroup$ – Ryan Castner Nov 4 '13 at 21:20

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$.

  • $\begingroup$ I know it's been a while since you replied to this. But could you please explain "There is always an equivalent walk in which no transition is taken twice in each pi" a bit more. I'm actually not clear. An example would be useful. Thanks! $\endgroup$ – markovuksanovic Nov 30 '13 at 3:04
  • $\begingroup$ Suppose the walk is of the form $p_1 e p_2 e p_3$, in which $e$ is taken twice. This walk can be replaced by $p_1 e p_3$. $\endgroup$ – Yuval Filmus Dec 1 '13 at 1:21
  • $\begingroup$ I think in the fifth line of the answer “no transition is taken twice in each $p_i$“ should be replaced with “no transition is taken twice in each $e_i$“ $\endgroup$ – Vinay Varahabhotla Jun 17 '20 at 11:34

|w| is the length of the input word being read for example if w=a then |w|=1 . if w=aaa then |w|=3 and Λ is the number of λ-edges in the graph.

for example to read the symbol a its 2+(1+2)*1=5 so all the walk to read a have a lentgh less or equal than 5

∂*(q0,a)={q1,q2,q0} of length 3≤5 because the path is q0->q1->q2->q0

∂*(q1,a)={q1,q2,q0} of length 5≤5 because the path is q1->q2->q0->q1->q2->q0

∂*(q2,a)={q1,q2,q0} of length 5≤5 because the path is q2->q0->q1->q2->q0

  • $\begingroup$ This is just a special case, far from a general proof. $\endgroup$ – vonbrand Feb 1 '16 at 22:41

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.