Search code examples
computation-theorynfa

In Non-Deterministic Finite Automata (NFA), how is the next branch/transition selected when there are two or more transitions?

For NFA, when there are 2 or more transition states, how does the machine decide which transition to take?

I was only able to find the "Guess and Verify" methodology, where we consider the system to be clairvoyant and always pick the correct path using binary trees.

Is this the only method? Could we also consider it as taking and existing in both states simultaneously?

Solution

  • You can consider it as trying all possible options, NFA accepts a word if there is a path from an initial state to an accepting state using this word.