A non-deterministic finite automaton (NDFA/NFA) is a 5-tuple (Q, Σ, δ, q0, F)
where,
Reference: Introduction to the Theory of Computation” by Michael Sipser
- 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.
Example of NFA,
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}
Reference:
- Introduction to the Theory of Computation” by Michael Sipser.