##### Non Deterministic Finite Automata | NFA is represented as a 5-tuple set (Q, ∑, ∆, q0, F)

In NFA, starting from a state, seeing the input we can go to various states or any particular states or null states; it gives us multiple options. Mostly these machines are abstract and conceptual. The machines used in daily life are deterministic automata. **NFA comes into the scenario when problems are solved backtracking method or brute force method (solve in every possible solution i.e., trial and error method).** Let me make easier, for example, our future or career cannot be pre-determined, studying engineering does not concludes that the person will end up as an engineer, he might fail or out of passion change his career track and end up as a painter; or in another situation, he might continue both the profession successfully like Leonardo da Vinci. In the same way, NFA works.

**NFA is represented as a 5-tuple set (Q, ∑, ∆, q _{0}, F)**

• Q → Set of states(Finite)

• ∑ → Set of input symbols.

• q_{0} → Start state

• F → Set of final states.

• Transition function ∆: Q×∑→2^{ Q}

__Example 1__: **Construct ****a NFA**** for all set of strings {a,b} ends with a.**

L(language) = {a, aa, ba, bbaa, babaa,…..}

Q={A,B}

∑= {a,b}

Where A is the initial state and B is the final state. In state A, after receiving input a, as it is Non-deterministic; it has options to choose, either it can go to state A or it can go to state B.

__Example 2__: **Construct NFA where set of all string of a’s followed by string of b’s**.

L= {ab, aabb, aaabbbb……a^{n}b^{n}| n, m>=1}

Q={q_{0,}q_{1,}q_{2}}

From the above diagram, we got 3 states- q0,q1,q2; where q_{0 }is the initial state and q_{2 } is the final state.

- In initial state q0 after getting a, NFA gives us possibilities either we can go to q0 or go to q1.
- In q1 after getting b, either go to state final state q2 or q1.

As compared to DFA, NFA is much easier to draw.

A non-deterministic machine can also be implemented by a deterministic machine. Every NFA is also a DFA. Therefore, whatever accepted by NFA should also be accepted by DFA.