Nondeterministic Finite Automaton

Nondeterministic Finite Automata (NFA) are a Finite automata where:

1. There may be many choice at one particular point
2. There may be no path spelling a given input
3. An input is accepted if at least one sequence of choices leads to an accepting state

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 automaton

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.