Differentiate between NFA and DFA

Difference between DFA and NFA

SR.NO.DFANFA
1DFA stands for Deterministic Finite AutomataNFA stands for Non-Deterministic Automata
2More, if NFA contains Q states then the corresponding DFA will have <= 2Q states.NFA has fever number of states
3DFA cannot use Empty String transitionNFA can use Empty String transition.
4DFA is as powerful as an NFANFA is as powerful as an DFA
5Difficult to design as transitions are deterministicEasy to design due to non-determinism.
6All DFA are NFANot all NFA are DFA
7The time needed for executing an input string is lessTime needed for executing an input string is more.
8It is easy to find whether w ϵ L as transitions are deterministic.It is difficult to find whether w ϵ L as there are several paths.
9In DFA, the next possible state is distinctly set.In NFA, each pair of state and input symbol can have many possible next states.
10DFA can be understood as one machineNFA can be understood as multiple little machine computing at the same time.
11DFA is more difficult to constructNFA is easier to construct

Deterministic finite Automata

The word “deterministic” refers to the fact that the transition is deterministic. There is only one state to which an automaton can transit from the current state each input. The word “finite” implies that number of state are finite. A finite automata consists of five parts:

  1. 1. A finite set of states, represented as Q.
  2. 2. A finite set of alphabet, represented as Σ.
  3. 3. An initial state, represented as q0 .
  4. A set of accepting states. An accepting state or final state is for ‘Yes’ answer. It is a subset of Q and is represented as F.
  5. F ⊆ Q
  6. 5. A next state function or a transition function. Next state depends on the current state and the current input. It is a function from Q X Σ to Q. It is repesented as δ .

Finite automata,

M = (Q, Σ, δ, q0, F), where

Q is a set of states.
Σ is a set of alphabet.
q0 ϵ Q is the initial state
F ⊆ Q is the set final states, and δ, the transition function, is a function from Q X Σ to Q.

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.

Differentiate between NFA and DFA
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})

Recommended:

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

Leave a Comment

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