The DFA are deterministic. It means that if a DFA reads in a state $c_i$ the symbol $\sigma_i$, the next state $c_{i+1}$ is fixed and pre-determined. There are also non-deterministic finite automata which can have many - or none - possible next states. A formal definition of such automata follows.
Definition: Non-deterministic Finite Automaton (NFA)
A non-deterministic finite automaton NFA) is a tuple $A=(C,\Sigma,\Delta,F,s_0)$, containing
- a finite set $C$ of conditions (or states),
- a finite input alphabet $\Sigma$,
- the state transition relation $\Delta\subseteq (C\times\Sigma)\times C$,
- the set of final states $F\subseteq C$, and
- the starting state $s_0\in C.$
We say that the NFA accepts an input word $\omega$ if and only if the NFA reaches a final state $q\in F$ after consuming $\omega,$ starting at $s_0\in S$.
The formal language $L(\operatorname{NFA})$ accepted by the NFA can be defined as a set of all words over the alphabet $\Sigma$, which can be consumed by the composition of the relation $\Delta$ with itself, starting from some state in $s_0\in S$, and ending at some state in $q\in F,$ formally: $$L(\operatorname{NFA}):=\{\sigma_0\sigma_1\ldots\sigma_n\in\Sigma^*\mid \exists s_0\in S,\; q=\Delta(\ldots\Delta(\Delta(s_0,\sigma_0),\sigma_1),\ldots,\sigma_n)\in F\}.$$
The class of all languages accepted by an NFA is denoted by $\mathcal L(\operatorname{NFA})$.
Notes
- The NFA is an acceptor since it has no output, only an input.
- Whether it can start or not with the input $\omega$, depends on the first symbol $\sigma_0$ of the input, and the definition of the transition relation $\Delta$ for the pair of values $(s_0,\sigma_0)$. If that transition relation $\Delta$ is not defined for this pair, the NFA cannot start accepting the word. This is one important difference to the definition of the DFA, in which the function $\delta$ is (since a function) a left-total relation. $\Delta$ can be any relation and does not have to be left-total.
- Another important definition is this: The relation $\Delta$ does have to be right-unique (like it was the case for the function $\delta$ in a DFA). This means that the new state $\Delta(s_0,\sigma_0)$ is not determined. Potentially, there might be many outcomes in the $i$th step of $\Delta(s_i,\sigma_i)$.
- Only accepted words $\omega=\sigma_0\sigma_1\ldots \sigma_{n-1}$ will lead to a state $s_n\in F.$ Non-excepted words will make the NFA get stuck in a loop at some non-final state, or the NFA won't even start at all.
- Whether or not the NFA accepts the empty word $\epsilon\in\Sigma^*$ can be read immediately from the definition of the NFA. This is the case if and only if $s_0\in F.$
Mentioned in:
Applications: 1
Definitions: 2
Examples: 3 4
Proofs: 5 6 7
Theorems: 8 9
Thank you to the contributors under CC BY-SA 4.0! 
- Github:
-
References
Bibliography
- Erk, Katrin; Priese, Lutz: "Theoretische Informatik", Springer Verlag, 2000, 2nd Edition
- Hoffmann, Dirk: "Theoretische Informatik, 3. Auflage", Hanser, 2015
