DFA Solved Examples | How to Construct DFA

Construction Of DFA-

 

Before you go through this article, make sure that you have gone through the previous article on Type-01 Problems.

 

Type-02 Problems-

 

In Type-02 problems, we will discuss the construction of DFA for languages consisting of strings starting with a particular substring.

 

Steps To Construct DFA-

 

Following steps are followed to construct a DFA for Type-02 problems-

 

Step-01:

 

  • Determine the minimum number of states required in the DFA.
  • Draw those states.

 

Use the following rule to determine the minimum number of states-

 

RULE

Calculate the length of substring.

All strings starting with ‘n’ length substring will always require minimum (n+2) states in the DFA.

 

Step-02:

 

  • Decide the strings for which DFA will be constructed.
  • The method for deciding the strings has been discussed in this Video.

 

Step-03:

 

  • Construct a DFA for the strings decided in Step-02.

 

Remember the following rule while constructing the DFA-

 

RULE

While constructing a DFA,

  • Always prefer to use the existing path.
  • Create a new path only when there exists no path to go with.

 

Step-04:

 

  • Send all the left possible combinations to the dead state.
  • Do not send the left possible combinations over the starting state.

 

PRACTICE PROBLEMS BASED ON CONSTRUCTION OF DFA-

 

Problem-01:

 

Draw a DFA for the language accepting strings starting with ‘ab’ over input alphabets ∑ = {a, b}

 

Solution-

 

Regular expression for the given language = ab(a + b)*

 

Step-01:

 

  • All strings of the language starts with substring “ab”.
  • So, length of substring = 2.

 

Thus, Minimum number of states required in the DFA = 2 + 2 = 4.

It suggests that minimized DFA will have 4 states.

 

Step-02:

 

We will construct DFA for the following strings-

  • ab
  • aba
  • abab

 

Step-03:

 

The required DFA is-

 

Problem-02:

 

Draw a DFA for the language accepting strings starting with ‘a’ over input alphabets ∑ = {a, b}

 

Solution-

 

Regular expression for the given language = a(a + b)*

 

Step-01:

 

  • All strings of the language starts with substring “a”.
  • So, length of substring = 1.

 

Thus, Minimum number of states required in the DFA = 1 + 2 = 3.

It suggests that minimized DFA will have 3 states.

 

Step-02:

 

We will construct DFA for the following strings-

  • a
  • aa

 

Step-03:

 

The required DFA is-

 

Problem-03:

 

Draw a DFA for the language accepting strings starting with ‘101’ over input alphabets ∑ = {0, 1}

 

Solution-

 

Regular expression for the given language = 101(0 + 1)*

 

Step-01:

 

  • All strings of the language starts with substring “101”.
  • So, length of substring = 3.

 

Thus, Minimum number of states required in the DFA = 3 + 2 = 5.

It suggests that minimized DFA will have 5 states.

 

Step-02:

 

We will construct DFA for the following strings-

  • 101
  • 1011
  • 10110
  • 101101

 

Step-03:

 

The required DFA is-

 

Problem-04:

 

Draw a DFA that accepts a language L over input alphabets ∑ = {0, 1} such that L is the set of all strings starting with ’00’.

 

Solution-

 

Regular expression for the given language = 00(0 + 1)*

 

Step-01:

 

  • All strings of the language starts with substring “00”.
  • So, length of substring = 2.

 

Thus, Minimum number of states required in the DFA = 2 + 2 = 4.

It suggests that minimized DFA will have 4 states.

 

Step-02:

 

We will construct DFA for the following strings-

  • 00
  • 000
  • 00000

 

Step-03:

 

The required DFA is-

 

Problem-05:

 

Construct a DFA that accepts a language L over input alphabets ∑ = {a, b} such that L is the set of all strings starting with ‘aa’ or ‘bb’.

 

Solution-

 

Regular expression for the given language = (aa + bb)(a + b)*

 

Step-01:

 

Minimum number of states required in the DFA = 5.

It suggests that minimized DFA will have 5 states.

 

Step-02:

 

We will construct DFA for the following strings-

  • aa
  • aaa
  • aaaa
  • bb
  • bbb
  • bbbb

 

Step-03:

 

The required DFA is-

 

Problem-06:

 

Construct a DFA that accepts a language L over input alphabets ∑ = {a, b} such that L is the set of all strings starting with ‘aba’.

 

Solution-

 

Regular expression for the given language = aba(a + b)*

 

Step-01:

 

  • All strings of the language starts with substring “aba”.
  • So, length of substring = 3.

 

Thus, Minimum number of states required in the DFA = 3 + 2 = 5.

It suggests that minimized DFA will have 5 states.

 

Step-02:

 

We will construct DFA for the following strings-

  • aba
  • abaa
  • abaab
  • abaaba

 

Step-03:

 

The required DFA is-

 

Also Read- Converting DFA to Regular Expression

 

To gain better understanding about Construction of DFA,

Watch this Video Lecture

 

Download Handwritten Notes Here-

 

 

Next Article- Minimization of DFA

 

Get more notes and other study material of Theory of Automata and Computation.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Summary
DFA Solved Examples | How to Construct DFA
Article Name
DFA Solved Examples | How to Construct DFA
Description
How to construct DFA- This article discusses construction of DFA with examples. DFA Solved Examples. DFA Construction Problems. Practice Problems based on Construction of DFA.
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-