**Definition**: An NFA is a 5-tuple or quintuple M = (Q, Σ, δ, q

_{0}, 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

_{0}∈ Q is the start state. A ⊆ Q is set of final states.

### Acceptance of language

**Definition**: Let M = (Q, Σ, δ, q

_{0}, 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

_{0}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

_{0}, w) = Q with atleast one Component of Q in A}

## No comments:

## Post a Comment