0
$\begingroup$

If a string(w) is accepted by an NFA, then corresponding to w, can there be multiple paths each starting from the start state and ending at an accepting state?

$\endgroup$
  • $\begingroup$ Alas, a bit late to invite you to present the results of your own efforts. $\endgroup$ – greybeard May 4 at 20:37
0
$\begingroup$

Yes, there can be many paths from the starting state to the ending state. It is not too difficult to cook up many trivial examples of when this happens, for instance

2 Path NFA

Clearly accepts the string $ab$ but it can go through either $s1$ or $s2$.

However, in DFA's this will never happen because at each state there is only a single possible transition for each character, and those fixed transitions uniquely determine the path.

| cite | improve this answer | |
$\endgroup$

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.