Non deterministic finite automata(NFA)

Definition: An NFA is a 5-tuple or quintuple M = (Q, Σ, δ, q₀, A) where

Q is non empty, finite set of states.

Σ is non empty, finite set of input alphabets.

δ is transition function which is a mapping from

Q x {Σ U ε} to subsets of 2^Q. This function shows

the change of state from one state to a set of states

based on the input symbol.

q₀ ∈ Q is the start state.

A ⊆ Q is set of final states.

Acceptance of language

Definition: Let M = (Q, Σ, δ, q₀, A) be a DFA where Q is set of finite states, Σ is set of input alphabets (from which a string can be formed), δ is transition function from Q x {ΣU} to 2^Q, q₀ is the start state and A is the final or accepting state. The string (also called language) w accepted by an NFA can be defined in formal notation as:

L(M) = { w | w ∈ Σ*and δ*(q₀, w) = Q with atleast one

Component of Q in A}