That&#x27;s only true in a naive implementation. In fact, in a naive implementation, it&#x27;s probably worse than that because there can be loops among epsilon transitions. Consider, for example, `(a{star}){star}`. (HN markup prevents use of a kleene star usefully. Sorry.)<p>In a &quot;real&quot; implementation, when computing the next set of states to visit for some position in the input, you explicitly avoid re-visiting states you&#x27;ve already seen <i>for that position in the input</i>. Cox talks about this quite a bit in his articles.<p>The guarantee of the NFA algorithm as presented by Cox is that each NFA state is visited <i>at most once</i> for each position in the input.