non-deterministic finite automaton
A non-deterministic finite automaton (or NDFA) can be formally defined as a 5-tuple , where
is a non-empty finite set of states,
is a function called the transition function,
is the starting state, and
is a set of final (or accepting) states.
Some authors also relax the fourth condition by permitting multiple starting states (see remark below).
Note how this definition differs from that of a deterministic finite automaton (DFA) only by the definition of the transition function . Operation of the NDFA begins at , and movement from state to state is governed by the transition function .
The transition function takes the first symbol of the (remaining) input string and the current state as its input, and after the transition this first symbol is removed only if the transition is defined for a symbol in instead of . Conceptually, all possible transitions from a current state are followed simultaneously (hence the non-determinism). Once every possible transition has been executed, the NDFA is halted. If any of the states reached upon halting are in for some input string, and the entire input string is consumed to reach that state, then the NDFA accepts that string.
An NDFA can be represented visually as a directed graph called the state diagram. Circular vertices denote states, and the set of directed edges, labelled by symbols in , denotes . The starting state is usually denoted by an arrow pointing to it that points from no other vertex. States in are usually denoted by double circles.
Consider the following regular language over the alphabet (represented by the regular expression
This language can be represented by the NDFA with state diagram: