Non-deterministic finite automaton (NFA) definition
Non-deterministic automaton is different from a deterministic one in that it can contain multiple transitions of the same letter from one state to other(s)
The second difference is that states can have no transitions with some letters. The absence of such a transfer means that the automaton can be “stopped” by sending input that arrives to such a state and tries to continue to a non-existing transfer
The language of such an automaton is defined as follows: Word is part of automaton language if and only if there exists a sequence of transitions such that automaton finishes in the accepting state
Stronger non-determinism
Equivalence of DFA and NFA theorem
NFA with
This is a variation of a non-deterministic automaton that allows changing the state without reading any input, it is denoted as a