Study of DFA, NFA and Its Comparison

A finite automaton (FA) is a machine(model) used to identify and recognize patterns within input taken from some character set and respond in a manner of whether the pattern will be accepted or rejected.

When you talk simply about a “Finite Automaton” then it may or may not be deterministic. One can only assume it is deterministic if it is specifically stated otherwise it is non-deterministic.

In this article, we will study specifically the automata without output i.e., Deterministic Finite Automata and Non-Deterministic Automata.

Formal Definition of DFA :

DFA is a deterministic finite automaton having a single resultant state from its corresponding input symbol. It comprises of 5 tuple such as, A = (Q, ∑, δ, q₀, F) .

(For better understanding refer and correlate terminologies with diagram )

• Q is a finite set of states {q₀,q₁,q_f}.
• ∑ is a finite set of symbols called the alphabet {0,1}.
• δ is the transition function where δ: Q × ∑ → Q
• q₀ is the initial state from where any input is processed (q₀ ∈ Q).
• F is a set of final states. Q (F ⊆ Q), {q_f ∈ Q}.

Graphical Representation of a DFA

A DFA is represented by digraphs called state diagrams or transition diagrams.

• The nodes in a circle represent the states.
• The arrows labeled with an input alphabet show the transitions.
• The initial state is denoted by a single incoming arrow.
• The final state is indicated by double circles (One inside the other).
• The transition in itself signifies a loop.
• Every state is deterministic with a set of input symbols.

Examples of DFA

Traffic Lights, Vending Machines, Video Games, Text Parsing, Regular Expression Matching, CPU Controllers, Protocol Analysis, Natural Language Processing, Speech Recognition

Non Deterministic Finite Automata

In NFA, there exist many paths for specific input from the current state to the next state. Where moves cannot be determined. Hence, it is called Non-deterministic Automaton. As it has a finite number of states, the machine is called a Non-deterministic Finite State Machine or Non-deterministic Finite Automaton.

Formal Definition of  NDFA :

An NDFA can be represented by a 5-tuple (Q, ∑, δ, q0, F) where −

• Q is a finite set of states.
• ∑ is a finite set of symbols called the alphabets.
• δ is the transition function where δ: Q × ∑ → 2^Q

(Here the power set of Q (2^Q) has been taken because in the case of NDFA, from a state, the transition can occur to any combination of Q states)

• q₀ is the initial state from where any input is processed (q0 ∈ Q).
• F is a set of final states/states of Q (F ⊆ Q).

For every NFA there's a corresponding DFA that accepts the same language, For NFA with n states, there would be DFA having Θ(2ⁿ) states. That is the reason why NFA is mostly preferred over DFA while designing a model of the machine.

Some  real-life examples of Non-Deterministic Automata are;

Games such as Tic Tac Toe, Ludo, Playing Cards, etc. all follow the NDFA approach in some another manner.

Now, let us understand both DFA & NFA by their comparison :

Basis of Difference	DFA	NFA
Path traversal for input	exist single paths for specific input from the current state to the next state	exist many paths for specific input from the current state to the next state
Empty string transition	DFA is not capable of using an Empty String transition.	NFA can use an empty String transition.
Structure	DFA can be best described and understood as one machine.	NFA is like multiple small machines that are performing computational activities at the same time.
Rejection of string	DFA rejects the string in case it terminates in a state that is different from the accepting state.	NFA rejects the string in the event of all branches dying or refusing the string.
Backtracking	Possible to use backtracking	It is not possible to use backtracking at all times in the case of NFA.
Level of construction	It's complex to construct DFA.	It is easy to construct.
Supremacy	All DFAs are derived from NFAs.	All NFAs are not DFAs.
Transition functions	The number related to the next state is one.	The number related to the next state/ states is either zero or one.
Complexities of time	The total time required for running any input string in DFA is less than what it is in NFA.	The total time required for running any input string in NFA is larger than that in comparison to DFA.
Space requirement	More space allocation is needed.	Less space is needed.
The setting of the next possible set	The next possible state is clearly set in DFA.	In NFA, every single pair of input symbols and states may contain many possible next states.

Enable GingerCannot connect to Ginger Check your internet connection
or reload the browserDisable in this text fieldEditEdit in GingerEdit in Ginger×

 Also, Study about: 

• Mealy Machine
• Moore Machine
• Rice Theorem
• Brief about Turing Machine
• Multi Dimension Turing Machine
• Multiple Turing Machine
• Parikh Theorem in TOC
• Parse Tree or Derivation Tree
• What do you Understand by Derivation
• MyHill Nerode Theorem
• Minimize Myhill Nerode Theorem
• Push Down Automata
• Know Where we use Automata
• What do you understand by Derivation of Grammar
• What is Context-free Grammar
• Example based on CFG
• Regular Expression in TOC
• What is Two-way infinite Turing machine?
• Example to generate Parse tree from the given grammar

Also Read, some interview tips

• Why Should I Hire You?
• What are your weaknesses?
• What are your greatest strengths?
• Tell me about yourself.
• What's the reason behind leaving your current position at your company?
• Do You Know how the power of Keywords impacts on Resume?
• Top 8 Proofreading Tips and Techniques in 2022.
• Top Ten Technical Resume Writing Tips in 2022.
• Tips for your resume before you get entry to Job Market
• What Questions you can ask HR during the Interview.
• How to make an impressive resume?
• Best Resume writing Technique.
• What Questions you can ask HR during the Interview.