Non-Deterministic finite Automata

Non-Determinstic finite automata can reside in multiple states at the same time. The concept of non -deterministic finite automata is being explained with the help of the transition diagram.

Non-Deterministic finite Automata
Transition Diagram of NFA

IF the automata is in the state q0 and the next input symbol is 1, then the next state will be either :

1) q0 2) q1

Thus, the move from q0 and the next input symbol is 1, cannot be determined uniquely. Such machines are called Non- deterministic automata.

– A Non- deterministic finite automata can be in several states at any time. Thus, NFA can guess about an input sequence.

– Every NFA can be converted into an equivalent DFA.

– An NFA can be designed with fewer states compare to its deterministic counterpart.

– Due to non-determinism, NFA take more time to recognize a string.

Definition of NFA

A Non – deterministic finite Automata is a 5 tuple.

                M = {Q, Σ, δ, q0, F}

                Q = A finite set states

                Σ = A finite set of input

                δ = A transition function from Q X Σ to the power set of Q i.e.to 2Q

                q0 = q0 ϵ Q is the start / initial state

                F = F Q is a set of final / accepting states.

The NFA, for table can be formally represented as,

({q0, q1, q2}, {0, 1},δ ,{q2})

where, the transition function δ is given below in table

Non-Deterministic finite Automata
Transition Table of NFA

Recommended:

  1. Introduction to Finite Automata
  2. DFA for Number of 1’s is even/odd and number of 0’s is even/odd
  3. DFA for number of 0’s divisible by five and 1’s divisible by 3
  4. DFA for All string of length at most five
  5. DFA for All strings ending with abb
  6. DFA for strings in which leftmost symbol differ from rightmost
  7. Design DFA that contain word ‘CAT’ using word ‘CHARIOT’
  8. Design DFA which accept a binary number divisible by 3
  9. Non-Deterministic finite Automata
  10. Design NFA to accept string containing the substring 0101
  11. Design NFA that accepts string ending with aab

Leave a Comment

Your email address will not be published. Required fields are marked *