If the basic finite automata model is modified in such a way that from a state on an input symbol zero, one or more transitions are permitted, then the corresponding finite automata is called a "non-deterministic finite automata" (NFA). Therefore, an NFA is a finite automata in which there may exist more than one paths corresponding to

* (because zero, one, or more transitions are permitted from a state on an input symbol). Whereas in a DFA, there exists exactly one path corresponding to

*. Hence, an NFA is nothing more than a finite automata:

### Acceptance of Strings by Non-deterministic Finite Automata

Since an NFA is a finite automata in which there may exist more than one path corresponding to *x* in Σ*, and if this is, indeed, the case, then we are required to test the multiple paths corresponding to *x* in order to decide whether or not *x* is accepted by the NFA, because, for the NFA to accept *x*, at least one path corresponding to *x* is required in the NFA. This path should start in the initial state and end in one of the final states. Whereas in a DFA, since there exists exactly one path corresponding to *x* in Σ*, it is enough to test whether or not that path starts in the initial state and ends in one of the final states in order to decide whether *x* is accepted by the DFA or not.

Therefore, if *x* is a string made of symbols in Σ of the NFA (i.e., *x* is in Σ*), then *x* is accepted by the NFA if at least one path exists that corresponds to *x* in the NFA, which starts in an initial state and ends in one of the final states of the NFA. Since *x* is a member of Σ* and there may exist zero, one, or more transitions from a state on an input symbol, we define a new transition function, δ_{1}, which defines a mapping from 2^{Q} � Σ* to 2^{Q}; and if δ_{1} ({*q*_{0}},*x*) = *P*, where *P* is a set containing at least one member of *F*, then *x* is accepted by the NFA. If *x* is written as *wa*, where *a* is the last symbol of *x*, and *w* is a string made of the remaining symbols of *x* then:

For example, consider the finite automata shown below:

where:

If *x* = 0111, then to find out whether or not *x* is accepted by the *NFA*, we proceed as follows:

Since δ_{1} ({*q*_{0}}, 0111) = {*q*_{1}, *q*_{2}, *q*_{3}}, which contains *q*_{3}, a member of *F* of the NFA—, hence, *x* = 0111 is accepted by the NFA.

Therefore, if *M* is a NFA, then the language accepted by NFA is defined as:

*L*(*M*) = {*x* | δ_{1} ({*q*_{0}} *x*) = *P*, where *P* contains at least one member of *F* }.