Nondeterministic Finite Automata (NFA) are a Finite automata where:
Every NFA has an equivalent Deterministic Finite Automata, however it’s expression may be significantly more complex in order to accept the same language.
When parsing an input and a state is reached with multiple ways to proceed, the computation branches with all valid transitions taken in parallel. Each of these continues as before, including splitting again if there are subsequent non-deterministic transitions. If the next input symbol does not have a transition, the related branch ends. Finally, if any one of the live branches lies in an accept state at the end of input, the NFA accepts the input string.
Generalised nondeterministic finite automata (GNFA) are NFA’s where the transitions may hold Regular expressions, instead of only members of the alphabet they are formed over.