'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

Author APURV RATHORE
2 upvotes
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up
Compiler Design

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.

Read About - Symbol Table Operations

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

Example

 

DFA

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' = ϕ
  • Add q0 to 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:

Illustration

 

State

a

b

q0

q1, q2

 

q1

   

q2

q1, q2

q2

 

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}

State

a

b

{q0}

{q1, q2}

 

 

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. 
Hence adding the transitions. 

State

a

b

{q0}

{q1, q2}

 

{q1, q2}

{q1, q2}

{q2}

 

Step 3:

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

State

a

b

{q0}

{q1, q2}

 

{q1, q2}

{q1, q2}

{q2}

{q2}

{q1,q2}

{q2}

 

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

DFA

Check out this article - Converting NFA to DFA

Frequently Asked Questions

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. 

Recommended Reading:

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!

Previous article
Nondeterministic Finite Automata
Next article
Lexer and Lexer Generators
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass