**Non-Deterministic Finite Automata (NFA)**

**Non-Deterministic Finite Automata (NDFA or NFA)** is an automata that accepts all regular languages, whether they are finite or infinite. So, all DFA are NFA but not vice versa.

**Very important In NFA is that,**

- Transition with the help of epsilon (empty string) is possible.
- There is no need to specify the transition of each input from any state.

**Formal Definition of NFA**

The following is the explanation of 5 tuples (Q, ∑, δ, q_{0}, F) of NFA where

**Q**represents a finite set of all states (q_{0, }q_{1, }q_{2, … }q_{n)}. Where n is a finite number**∑**represents a finite set of symbols called the alphabet. i.e. {0, 1}.- δ: Q x ∑ → 2
^{Q}represents a transition function **q**represents the initial state from where any input is processed (q_{0 }_{0}∈ Q).**F**represents a set of final states/states where F will be a subset ( ⊆ ) of Q.

## Non-Deterministic Finite Automata **(****NFA)** Representation

### Non-Deterministic Finite Automata (NFA) examples can be represented either with epsilon or without epsilon. Let’s explain both of these

**1. Example of NFA with Epsilon**

The following is an example of Non-Deterministic Finite Automata with epsilon that accepts a string 10 or epsilon.

The following is the explanation of 5 tuples of the above-given NFA

{Q {q0, q1, q2}, **∑** {0, 1}, δ, S {q0}, F {q2} }

where,

- {q0, q1, q2} are set of states
- {0, 1} are the set of input alphabets
- δ refers to the transition function
- q0 refers to the initial state
- {q2} refers to the set of final state

**Transition function δ is defined as**

- δ (q0, 1) = q1
- δ (q0, ∈) = q2
- δ (q1, 0) = q2

**The following table shows the Transition for the above Non-Deterministic Finite Automata. **

States / Alphabets |
0 |
1 |
∈ |

q0 |
– | q1 |
q2 |

q1 |
q2 |
– | – |

q2 |
– | – | – |

**2. Example of NFA without Epsilon**

The following is an example of Non-Deterministic Finite Automata without epsilon that accepts a string 10 or 1.

The following is the explanation of 5 tuples of the above-given NFA

**{ Q{ q0,q1,q2}, ∑{0,1}, δ, S{q0}, F{q2} } where **

- {q0,q1,q2} are set of states
- {0,1} are set of input alphabets
- δ refers to the transition function
- q0 is the initial state
- {q2} represent the final state

**Transition function δ can also defined as**

- δ (q0, 1) = q1
- δ (q0, 1) = q2
- δ (q1, 0) = q2

**The transition Table for the above NFA is**

States / Alphabets |
0 |
1 |

q0 |
– | q1, q2 |

q1 |
q2 |
– |

q2 |
– | – |

**Equivalence of DFA and NFA**

- Two finite automata accepters are considered equal in power if they both accept the same language.
- DFA and NFA both accept similar languages because
**DFA and NFA can be constructed for any regular language.**So, both are exactly equal in power.

__Important__

- Every NFA is converted into its equivalent DFA.
- Every DFA is an NFA, but not every NFA is a DFA.

Let’s learn some basic examples of NFA