World's most popular travel blog for travel bloggers.

Why do these NFAs need epsilon transitions?

, , No Comments
Problem Detail: 

In the picture below, I'm trying to figure out why there's a need of epsilon in there and what would be the difference if we didn't put epsilon.

enter image description here

Asked By : Barte
Answered By : Raphael

They do not make a difference. In fact, we don't need epsilon transitions, in the strict sense. Even though they can not be just left out in general, they can always be replaced by several edges using the epsilon closure (cf. the powerset construction).

These examples most likely stem from Thompson's construction, a simple algorithm that creates an NFA equivalent to a given regular expression. It uses epsilon transitions to link recursively constructed subautomata together.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback