Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Representation of DFA
3.
Transition table
4.
Need of Deterministic Finite Automata
4.1.
Dead state in DFA
5.
How Can I Use Deterministic Finite Automata?
6.
Converting NFA to DFA
7.
Frequently Asked Questions
7.1.
What are the properties of DFA?
7.2.
Can DFA have multiple final states?
7.3.
Can DFA be converted to NFA?
7.4.
Which language is accepted by deterministic finite automata?
8.
Conclusion
Last Updated: Jun 16, 2024
Easy

Deterministic Finite Automata (DFA)

Author APURV RATHORE
2 upvotes

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

Deterministic Finite Automata

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

FromNext State from input 0Next State from input 1
s1s2s1
s2s1s2

 

DFA

Source

A DFA is a state machine built up of states and transitions that can accept or reject a finite string made up of a series of symbols and evaluate it to a predefined language across a predefined set of characters. We represent states with circles and transitions with directed arrows. Every state must have each symbol radiating from it, or it will not be characterized as a DFA. The machine is known as a Deterministic Finite Machine since it has a finite number of states.

Let us take an example to understand it in a better way:

Consider a machine that accepts strings containing at least one a from the alphabets a and b.

In the above picture, the initial state of the machine is q0, and the final state of the machine is qf, the state which determines whether the string is accepted or not.

Assume we have the string 'ba.'

The letter 'b' is the first to enter the system.

As it can be seen in the diagram above when b enters the system, it is accepted by q0 and remains there. When we give the machine the symbol a, we can see that when q0 accepts a, it proceeds to the final state, qf. (The double circles represent the final state.)

The string a is accepted by the machine and the string has ended, we can conclude that the given string is accepted by the DFA.

Also read - Arden's theorem

Transition table

The transition table is a table that shows how the transition function works. It takes two inputs (a state and a symbol) and outputs a state (the "next state").

The following elements make up a transition table:

The input symbols are represented by columns.
States are represented by rows.
The next state corresponds to the entries.
An arrow with no source denotes the start state.
A star indicates the accepted state.
 The transition table for the same DFA is following:

Present StateNext State from input aNext State from input b
→q0qfq0
*qfqfqf

Need of Deterministic Finite Automata

DFAs make it much easier to use certain projects and applications that switch between valid and invalid states. DFAs are useful in the functionality of applications such as

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

 

Let us see one more example to understand DFA.

Design a DFA over the input alphabets {a,b} which accepts all strings that end with a.

Step 1: Consider the strings {a,aa,ba,aba,bba………} that follow the above condition.

We can derive from the preceding example that any number of alphabets can come before a.

 

Step 2: Design the DFA for the lowest possible string.

DFA

As we can see, in order to answer the question, we need a machine that accepts strings that end in a, it doesn’t matter what is the starting of the string, only the ending string should be a. Because our condition only involves one symbol, we have only one necessary transition, so we take two states. In this case, the string can begin with any symbol but must end with an a. As a result, any presence of b is directed to q0, which is our initial state, whereas a's are directed to the final state qf, which is the final state of the DFA.

The transition table for the above DFA is as followed:

Present StateNext State from input aNext State from input b
→q0qfq0
*qfqfq0

Dead state in DFA

If the machine has successfully progressed to the final string accepting state, we can say that the string has been accepted by the DFA.

However, if we arrive at a point where the machine can no longer progress to its final state, we have arrived at a dead state. A Dummy state is another name for a dead state.

Let us look at the following example to understand the dead state in a better way

Dead State

 

In this example, the machine will begin, and if we want to read strings that begin with 0, the machine will reach its final state B, which will allow it to accept a string.

However, if we start the machine with 1, it will not be able to advance to the final state. It will reach another intermediate state which is C. We are now in a dead state after reading 1. And the string will not be accepted by DFA.

The transition table for the above DFA is as followed:

Present StateNext State from input aNext State from input b
→ABc
CNo TransitionNo Transition
*BBB

Check out this article - Converting NFA to DFA

How Can I Use Deterministic Finite Automata?

Deterministic Finite Automata (DFA) are used in various applications across computer science and related fields due to their ability to model and recognize patterns defined by regular languages. Here’s how DFA can be effectively utilized:

  • Pattern Matching: DFA can be employed to search for specific patterns within strings or texts efficiently. By constructing a DFA that represents the pattern to be found, you can traverse the input text and determine if the pattern exists, and where it occurs.
     
  • Lexical Analysis: DFA are extensively used in compilers and interpreters for lexical analysis, also known as tokenization. Tokens such as keywords, identifiers, operators, and literals in programming languages are typically recognized using DFA. Each token type is represented by a DFA that defines its structure and rules.
     
  • String Validation: DFA can verify whether a given string adheres to a specified format or syntax. For instance, validating email addresses, phone numbers, URLs, or any structured data format can be efficiently handled using DFA.
     
  • Finite State Machines (FSM): DFA serve as the fundamental building blocks for designing more complex finite state machines. FSMs are widely used in control systems, protocol design, circuit design, and modeling sequential logic.
     
  • Regular Expression Matching: DFA can be implemented as part of engines that process regular expressions. Regular expressions define patterns that describe sets of strings, and DFA can recognize these patterns efficiently.

In practice, DFA are implemented programmatically using states, transitions, and an input alphabet. They offer fast processing times and deterministic behavior, making them suitable for real-time systems and applications requiring efficient pattern recognition and validation.

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 are the properties of DFA?

A Deterministic Finite Automaton (DFA) has a finite set of states, a single initial state, a finite input alphabet, and a transition function that uniquely determines the next state for each input symbol. It also has a set of accept states where the machine halts.

Can DFA have multiple final states?

Yes, a DFA can have multiple final states. The string is accepted if it leads to any of these final states after processing all input symbols. This flexibility allows DFAs to recognize a broader range of languages and patterns.

Can DFA be converted to NFA?

Yes, any DFA can be transformed into (and is already) an NFA.

Which language is accepted by deterministic finite automata?

A language L is accepted by a DFA < Q , , q0 , , A > , if and only if L = { w | *( q0 , w ) A } . That is, the language accepted by a DFA is the set of strings accepted by the DFA.

Conclusion

This article has covered a detailed explanation of Deterministic Finite Automata (DFA) and how it can be converted into Non-deterministic Finite Automata (NFA). We hope this information has helped you understand DFA better. Check out more of our DFA articles for further learning, and please support us by upvoting our blog to help others learn too.

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.

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 Code 360.

Happy Coding!

Live masterclass