NonDeterministicFiniteAutomata.md (862B)
1 # Non-deterministic Finite Automata (NFA) 2 3 **Source:** Theory of Computation 4 5 **Lecture:** 3 6 7 **Definition:** A NFAs differ from DFAs in the following ways: 8 9 1. DFA must have transitions for each symbol whereas a NFA might not. 10 2. It is possible for a NFA to have a state transition with a label of epsilon, indicating such a transition has no impact upon the current word. 11 3. An NFA may have a state with multiple transitions for the same symbol. 12 13 --- 14 15 As we can see, an all DFAs can be considered NFSs, but the opposite is not true. 16 17 When evaluating a NFA, if the machine runs into a split where it can either take one option or the other option, it creates a split (copy) and runs both in parallel. If the next input symbol does not appear on any of the arrows exiting the state occupied by the copy, the copy dies. 18 19 A good way to think of NFAs is as a tree.