Nondeterministic Automata
The definition of nondeterministic automata(NFA) just means that at a given character and state, the next state could be ambiguous. More formally, in state $q_0$, on symbol $a$, the choice of next state is not unique: could be either $q_0$ or $q_1$. What follows is that some states can have no next states, and will not process additional symbols.
We know that the deterministic function of a deterministic automata will give you the next state when given the current state and processed character. However, a nondeterministic function will return a set of multiple possible future states(or none) given a current state and character.
When a nondeterministic automata comes to a fork, where it has multiple possible ways it could go, we treat those as separate execution paths. This means that a nondeterministic automata could possibly have multiple execution paths, all of which need to be considered when analyzing it.
We consider a string $s$ to be in the language of an NFA $M$ if and only if there exists at least one successful execution of $M$ on $s$. Generally we simulate this by simulating an execution tree on a string. You can also instead compute the set of all possible states after processing each input symbol(think of it like a BFS).
Defining an NFA
A nondeterministic finite automata $M$ consists of:
- A finite set of states $Q$
- A finite alphabet $\Sigma$
- An initial state $q_0$ that belongs to $Q$
- A subset $F$ of $Q$, called accepting states
- A transition function $\Delta: Q \times \Sigma \to 2^Q$
Note that NFAs don’t follow computational models of Turing machines, which can only execute one path at a time. Despite this, NFAs are important to study as they are critical to the theory of NP-complete problems and regular expressions.