'Coding has over 700 languages', '67% of programming jobs arenâ€™t in the technology industry', 'Coding is behind almost everything that is powered by electricity'
Last Updated: Jun 30, 2023

# Deterministic Finite Automata

APURV RATHORE
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems

## Introduction

A deterministic finite automaton (DFA) is a finite-state machine that accepts or rejects a given string of symbols by running through a state sequence that is uniquely determined by the string in the theory of computation.

For each input symbol, the state to which the machine will move can be determined using DFA. It's called as a Deterministic Automaton as a result of this. As it contains a finite number of states, the machine is called a Deterministic Finite Machine or Deterministic Finite Automaton.

## Representation of DFA

It is represented as 5 tuples (Q, âˆ‘, Î´, q0, F) where:

• Q represents the finite states
• âˆ‘ represents the is a finite set of symbols, also called the alphabet
• Î´ represents the transition function where Î´: Q Ã— âˆ‘ â†’ Q
• q0 represents the initial state from where any input is processed
• F represents the set of final state of Q.

Example:

The following is an example of a DFA M with a binary alphabet that accepts an even number of 0s in the input.

M = (Q, Î£, Î´, q0, F) where

• Q = {S1, S2}
• q0 = S1
• Î£ = {0, 1}
• F = {S1}

Î´ is represented by the following table

Source

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## Converting NFA to DFA

We'll go over how to convert NFA to its DFA equivalent in this section. The machine changes states when a specific input is supplied to the current state in NFA. It can have zero, one, or several motions on a single input symbol. In DFA, however, when a specific input is given to the current state, the machine only goes to one state. DFA can only make one move on each input symbol.

Suppose M is an NFA denoted by M = (Q, âˆ‘, Î´, q0, F). We need to create an DFA M' = (Q', âˆ‘', q0', Î´', F') such that L(M) = L(M').

Follow the below steps to convert the NFA to dfa:

• Initially Q' = Ï•
• Loop over each of the states in Qâ€™ and for each possible input, find the set of states after the transition
• The final state of the DFA will be all the state containing F which is the final state of NFA M.

Example:

Step 1:

The initial start state of the DFA will be Qâ€™. Initially Qâ€™ = {q0}

The state q0 on input a goes to both the state q0 and q1, hence we form a new state {q0,q1}

Step 2:

Now we define transition for our new state {q1,q2}. q2 on a goes to q2 and q1 and q2 on b go to q2.

Step 3:

Now we define transition for our new state {q2}.
Hence after adding the transitions, we get.

Hence our final state will be {q1,q2} and start state will be {q0}.

### What is Deterministic Finite Automata?

Operators are special symbols that are used to operate on two or more variables and return the result of the operation.

### What is Non-deterministic Finite Automaton?

In NDFA, the machine can travel to any combination of the states in the machine for a given input symbol. To put it another way, the precise state to which the machine moves cannot be predicted. As a result, it's known as a Non-deterministic Automaton. The machine is known as a Non-deterministic Finite Machine or Non-deterministic Finite Automaton because it has a finite number of states.

## Conclusion

In this article, we have extensively discussed Deterministic Finite Automata and its conversion into NFA. We hope that this blog has helped you enhance your knowledge regarding DFA and if you would like to learn more, check out our articles on DFA. Do upvote our blog to help other ninjas grow.

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Coding!

Guided path
Free
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems