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 2Q.
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.