Want to contribute? Click here to suggest edits or additions.

Formal Defn of an NFA

M = ( Q, Σ, δ, q₀, F )

δ : Q × (Σ ∪ {ϵ}) → 𝒫(Q)

An NFA N accepts a string s = w₁w₂w₃…w_n iff ∃ a sequence of r₀r₁…r_n ∈ Q such that r_n ∈ F and r_i+1 ∈ δ(r_i, w_i)

Equivalence of NFA and DFA

Theorem: L is regular iff it can be recognized by an NFA.

Proof:

If L is recognisable by a NFA (let) N = (Q, Σ, δ, q₀, F)

Consider the DFA, D = (Q’, Σ, δ’, q₀’, F’) where -

• Q’ = 𝒫(Q)
• δ’ : Q’ → Q’ and
  • δ’(A, c) → ⋃ E(δ(a,c)), where
    • a∈A
    • E(A) = the set of states connected to some q∈A by ϵ. Trivially, some qs map to themselves via a ϵ.
• q₀’ = E(q₀)
• F’ = {A’∈Q’ | A∩F ≠ ∅}

If S is accepted by N iff ∃ r₀…r_n ∈ Q r₀=q₀ and r_i+1 ∈ δ(r_i, w_i)

⟹ r_i+1 ∈ R_i = E(δ(r_i, w_i)) and r_n ∈ R_n ∈ F.