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, ∑, ∆, q0, F) 

• Q → Set of states(Finite)

• ∑ → Set of input symbols.

• q0 → 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……anbn| n, m>=1}

Q={q0,q1,q2}

From the above diagram, we got 3 states- q0,q1,q2;  where q0 is the initial state and q2  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.

Contributor's Info

Created: Edited:
0Comment