Nondeterministic finite automaton

Summary

A nondeterministic finite automaton (NFA) is a finite automaton in which a state may have several transitions, or none, for the same input symbol. It accepts a word when at least one of its possible runs on the word ends in an accepting state. Every deterministic finite automaton is an NFA, and by the powerset construction every NFA can be turned into a DFA that accepts the same language. NFAs are often much smaller and easier to build than equivalent DFAs, for example when translating regular expressions into automata.