A non-deterministic finite automaton (NDFA/NFA) is a 5-tuple (Q, Σ, δ, q0, F)

where,

Q = is a finite set of states.

Σ = is a finite set of input symbols.

δ = is a transition function mapping from Q × Σ to 2^{Q}.

q0 = is the initial state, q0 ∈ Q.

F = is a set of final states, F ⊆ Q.

**For example,**

Consider the NFA that accepts all string ending with 01.

In this NFA,

M = {Q, Σ, δ, q0, F}

where,

Q = {q0, q1, q2}.

Σ = {0, 1}.

δ = As shown above.

q0 = Initial state.

F = {q2}

**Some terms in NFA:**

**Alphabet:** An alphabet is a finite, non-empty set of symbols.

Generally “Σ” is used to devote the alphabet.

For example,

Σ = {0, 1}

Σ = {a, b}

**Symbol:** Any character, number or special symbol can be treated as a “symbol”. It is the member of the alphabet.

For example,

In above alphabet 0, 1 is symbol.

**Word:** A word or string is a finite sequence of symbols.

For example,

S = 0110

S = ababa.