closuresautomatanfaepsilon

What will be the e-closure(r) in following NFA


Sorry guys I cannot provide the pic here...I was unable to upload the pic...so.. I will give the transition table of the problem.

(S/I)....a...b.....c.......e(elipson) 


p>.......{p}.....{q}...{r} ..¤(phi) 


q>.......{q} ....{r} ..¤.... {p} 


r(final)>..{r}...¤....{p}....{q} 

Here ¤ is phai
p is starting state
And r is final state

My doubt is...Will e-closure of final state {r} have starting state {p}......,even if starting state will not have a direct reach through elipson to final state .....but...final state reach the starting state through elipson to state {q} and then to starting state {p}

In my book it is given that

e-closure (r)={r,q} 

But my question is why it is not ....{p,q,r}...while final state {r} is reaching starting state {p} as well...


Solution

  • ϵ-closure(s) is a set of NFA states reachable from NFA state s on ϵ-transitions alone.

    You were correct in thinking the same. Please follow the definition mentioned above.

    So, ϵ-closure(r) = set of NFA states reachable from NFA state r on ϵ-transitions alone = {p,q,r}. Hence, your book has incorrectly computed it.

    The answer has to be {p,q,r}.

    NOTE that state {r} is included because a state will always remain on itself at ϵ-transition. State {p} was possible because p is reachable from NFA state q on ϵ-transition, which was reachable from NFA state r on ϵ-transition.