Peter Linz Edition 4 (Page No. 52)

Question

Help me understand  this statement from Theory of Computation by Peter Linz

"If between two vertices vi and vj 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. 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."

 

I am also having  difficulty in understand  extended  transition function  for an  nfa  , would be really helpful if someone could explain that.

Comments

@ankit singh,What you couldn't understand brother?

---

i did not understand  this  sentence  at all sir  , I was studying  the book by myself  and  extended  transition function for  dfa made  sense  .  But  the author  tried  to do the same thing with NFA  and I couldn't  understand  at all what he wanted  to do  ,  please explain this to me if possible  as I have stopped  studying TOC entirely  as I can't get across this statement  .

Answer 1

Extended Transition Function for NFA with $(\epsilon )$ - Transitions 

For single input symbols extended transition function behaves same as normal transition function in case of DFA and NFA without  $(\epsilon )$ - Transitions. 

But not in case of NFA with $(\epsilon )$ - Transition. 

Remember this,

$\epsilon $-closure({q1,q2,...qn})=$\epsilon $(q1)$\bigcup$$\epsilon $(q2)$\bigcup$....$\bigcup$$\epsilon $(qn)

Now applying the above rule in the example given in fig:-

$\epsilon $-closure({q0,q1,q2,q3})=$\epsilon $(q1)$\bigcup$$\epsilon $(q2)$\bigcup$$\epsilon $(q0)

={{q0,q1,q2,q3}$\bigcup${q2}$\bigcup${q0,q3}. 

After having taken the union of the above sets we finally get,
={q0,q1,q2,q3}

Comments

I hope the above explanation helps you brother. If u still haven't understood share ur doubts in comments.