Nondeterministic Finite Automaton - Formal Definition

Formal Definition

An NFA is represented formally by a 5-tuple, (Q, Σ, Δ, q₀, F), consisting of

• a finite set of states Q
• a finite set of input symbols Σ
• a transition relation Δ : Q × Σ → P(Q).
• an initial (or start) state q₀ ∈ Q
• a set of states F distinguished as accepting (or final) states F ⊆ Q.

Here, P(Q) denotes the power set of Q. Let w = a₁a₂ ... a_n be a word over the alphabet Σ. The automaton M accepts the word w if a sequence of states, r₀,r₁, ..., r_n, exists in Q with the following conditions:

1. r₀ = q₀
2. r_i+1 ∈ Δ(r_i, a_i+1), for i = 0, ..., n−1
3. r_n ∈ F.

In words, the first condition says that the machine starts in the start state q₀. The second condition says that given each character of string w, the machine will transition from state to state according to the transition relation Δ. The last condition says that the machine accepts w if the last input of w causes the machine to halt in one of the accepting states. Otherwise, it is said that the automaton rejects the string. The set of strings M accepts is the language recognized by M and this language is denoted by L(M).

We can also define L(M) in terms of Δ*: Q × Σ* → P(Q) such that:

1. Δ*(r, ε)= {r} where ε is the empty string, and
2. If x ∈ Σ*, a ∈ Σ, and Δ*(r, x)={r₁, r₂,..., r_k} then Δ*(r, xa)= Δ(r₁, a)∪...∪Δ(r_k, a).

Now L(M) = {w | Δ*(q₀, w) ∩ F ≠ ∅}.

Note that there is a single initial state, which is not necessary. Sometimes, NFAs are defined with a set of initial states. There is an easy construction that translates a NFA with multiple initial states to a NFA with single initial state, which provides a convenient notation.

For more elementary introduction of the formal definition see automata theory.