Non Deterministic Finite Acceptor (NFA):


An NFA is defined by the quintuple  M = (Q, ∑ , δ,  q0, F)

Q  is a finite set of initial states.

is a finite set of symbols called the input alphabet.

q0  Q is the initial state

F ⊆ Q  is the set of final states

δ: Q X (Σ ∪ {λ}) → 2Q or P(Q)

[It also has input alphabet λ i.e. it has moves for λ]


Language accepted by NFA (M) is the set of all strings accepted by M.

  • ∀ω ∊ L, δ*(q0, ω) ∩ F ≠ ϕ (string ω accepted)
  • ∀ω ∉ L, δ*(q0, ω) ∩ F = ϕ ( string ω rejected)