Nondeterministic Finite-State Machine
A nondeterministic finite-state machine (NFA) is not wholly disimilar to a DFA, however unlike a DFA from any pairing of state and input symbol there may be more than one valid next state. An NFA accepts a string of symbol inputs, and for each symbol it transitions to a next state until there are no more symbols. Unlike a DFA however the next state is not determined any may be any state of a given set of states. When all the inputs symbols have been processed, an NFA will accept if any valid set of transitions resulted in an accept state.
The example above shows an example of an NFA, in this case the NFA accepts any word that contains 101 or 11 as substrings. At each state where the current input symbol could lead to one or more next states, execution branchs and continues on each branch until it ceases - either as a result of not having a next state, or terminating on an accept state.
It is worth noting the introduction of the empty input, 
which means you can progress to the next state without considoring the input at all.
Formally, an NFA is defined as 
such that
is a finite set of states (in the example 
)
is a finite alphabet
is the transient function.
is the start state
is the set of accept states (in the example, 
)
Conversion Between NFA and DFA
From this formal definition, it can be formally shown that for any given DFA, an NFA can be constructed and vice-versa. From an NFA, a DFA can be constructed from the powerset of all states of the NFA, meaning there will be a maximum of 
states in the DFA, where 
is the number of states in the NFA. Once the initial DFA has been constructed though, simplifications will become apparant that may render some states unnecessary.