Examples of DFA

This lecture discusses more than 20 examples of DFA. But you make sure that you have already covered the topic of DFA. There are six different categories are selected for examples of DFA, which are listed below

  • Accept Only given Input
  • Start and Ends with
  • Contains string
  • Specific Length
  • Divisibility
  • Even and odd string

Let’s explain all of these DFA examples in sequence in TOC. 

Example 1:

Design a DFA over ∑ = {0, 1} that accepts the only input a string “10”.

Solution:

In the above example, the language contains only one string given below

L= {10}

DFA that accepts the only input a string “10” is given below

Examples of DFA (1)

Example:2

Construct a DFA with ∑ = {a, b} that accepts the only input “aaab”.

Solution:

The given question provides the following language

L= {aaab}

The following diagram represents the DFA accepter for L= {aaab}.

Examples of DFA (2)

Example:3

Construct DFA, which accept all the string over alphabets ∑ {0,1} that start with “0”.

Solution:

The given question provides the following language

L = {0, 01, 00, 010, 011, 000, 001,…, }

Let’s draw the DFA, which accepts all the strings starting with “0”.

Construct DFA that starts with 0

Example:4

Construct DFA, which accept all the string over alphabets ∑ {0,1} that start with “01”.

Solution:

The given question provides the following language

L = {01, 010, 011, 0100, 0101, 0110, 0111}

Let’s draw the DFA which accepts all the strings of the above language

DFA Example that start with “01”

Example:5

Construct DFA, which accepts all the strings over alphabets ∑ {0,1} that ends with “0”.

Solution:

The given example provides the following language

L = {0, 10, 00, 000, 010, 100, 110, …, }

Let’s draw the DFA, which accepts all the strings that end with “0”.

Examples of DFA that ends with “0”

Example:6

Construct DFA, which accept all the string over alphabets ∑ {0,1} that end with “10”.

Solution:

The given question provides the following language

L = {10, 010, 110, 0010, 0110, 1010, 1110,…., }

 DFA, which accepts all the strings that end with “10” is given under

Examples of DFA that ends with 10

Example:7

Construct a DFA with sigma ∑ = {0, 1}, accepts those string which starts with one and ends with 0.

Solution:

The given question provides the following language

L= {10, 1100,1010, 1110, 100010, 1000101110,…, }

The following diagram represents the DFA accepter for the above language.

Examples of DFA (3)

Note: The above automata machine does not accept those strings that start and end with the same input as “10001”.

Example:8

Construct DFA, which accepts all the strings over ∑ {0,1} where each contains “0”.

Solution:

The given question provides the following language

L= {0, 01, 10, 00,001,101,000, …., }

Let’s draw the DFA, which accepts all the strings containing “0”.

Examples of DFA where each string contains “0” as a substring

Example:9

Construct DFA, which accept all the string over alphabets ∑ {0,1} where each string contains “00”.

Solution:

The given question provides the following language

L= { 00, 000, 100, 001, 1100, 0011, 0010, 1001,……, }

Let’s draw the DFA which accepts all the strings of the above language

Examples of DFA each string contains “00” as a substring.

Example:10

Construct a DFA with sigma ∑ = {0, 1}, accepts all strings that contain three consecutive 0’s.

Solution:

The given question provides the following language

L= {000, 1000,0001, 111000, 10001, …, }

 DFA, which accepts all the strings that contain three consecutive 0’s, is given under

Examples of DFA (4)

Example:11

Construct DFA, which accept all the string over alphabets ∑ {0,1} where each string contains “101” as a substring.

Solution:

The given question provides the following language

L= {101, 0101, 1101, 1010, 1010, 01010, 01011,……, }

Let’s draw the DFA which accepts all the strings of the above language

Examples of DFA where each string contains “101” as a substring.

Example:12

Construct DFA, which accept all the string over alphabets ∑ {0,1} where the length of each string is exactly 2.

Solution:

The given question provides the following language

L= {00, 01, 10, 11}

The following diagram represents the DFA accepter for the language language where the length of each string is exactly two.

Draw a DFA where length of each string is exactly 2

Example:13

Construct DFA, which accept all the string over alphabets ∑ {0,1} where the length of each string is ≥ 2.

Solution:

The given question provides the following language

L = {00, 01, 10, 11, 000, 011, 010, 100, 101, 111, 0000, ……, }

The following diagram represents the DFA accepter for the language language where the length of each string is ≥ 2.

Examples of DFA where length of each string is ≥ 2 

Example:14

Construct DFA, which accept all the string over alphabets ∑ {0,1} where the length of each string is ≤ 2

Solution:

The given question provides the following language

L = {0, 1, 00, 01, 10, 11}

The following diagram represents the DFA accepter for the language where the length of each string is ≤ 2

 

Examples of DFA the length of each string is ≤ 2

Example:15

Construct DFA, which accept all the string over alphabets ∑ {0,1} where the length of each string is EVEN.

Solution:

The given question provides the following language

L = {00, 01, 10, 11, 0000, 1111, 0011, ……, }

The following diagram represents the DFA accepter for the language where the length of each string is even.

Examples of DFA the length of each string is EVEN

Example:16

Construct DFA, which accept all the string over alphabets ∑ {0,1} where the length of each string is ODD.

Solution:

The given question provides the following language

L = {0, 1, 000, 111, 011, 100, ……, }

The following diagram represents the DFA accepter for the language where the length of each string is odd.

Examples of DFA where length of each string is ODD

Example:17

Construct DFA, which accepts all the string over alphabets ∑ {0,1} where binary integers divisible by 3

Solution:

The given question provides the following language

L = {0, 11, 110, 1001, 1100, 1111, ……, }

The explanation for string 1001 is given below.

1001= 9, 9/3 = 3; hence, 1001 is divisible by 3.

The following diagram represents the DFA accepter for the language where binary integers are divisible by three.

Examples of DFA where binary integers divisible by 3

Example:18

Construct DFA, which accepts all the string over alphabets ∑ {0,1} where binary integers divisible by 4

Solution:

The given question provides the following language

L = {0, 100, 1000, 1100, 10000,……, }

The explanation for string 10000 is given below.

10000= 16, 16/4 = 4, hence 10000 is divisible by 4.

The following diagram represents the DFA accepter for the language where binary integers are divisible by four.

Examples of DFA where binary integers divisible by 4

 

DFA Example 19:

Draw a DFA for the language that accepts strings containing neither ’00’ nor ’11’ as a substring over the input alphabet ∑ = {0, 1}.

Solution:

The given question provides the following language (L) and DFA diagram

L={0,1,10,010,1010,01010,101010,0101010,10101010,010101010,…..} 

Solved example number 19 of DFA - updated

DFA Example 20:

Design a DFA that accepts strings with ’01’ or ’10’ as a substring over input alphabets ∑ = {0, 1}.

Solution:

The given question provides the following language (L) and DFA diagram

L={001,110,1110,0010,0001,1101,…..}

 

Solved example number 20 of DFA

DFA Example 21

Construct a DFA with sigma ∑ = {0, 1} for the language accepting strings ending in either ’01’ or ’10’.

Solution:

The given question provides the following language (L) and DFA diagram

L={01,10, 010, 101, 001, 110…..}

 

Solved example number 21 of DFA

DFA Example 22

Construct a DFA with sigma ∑ = {0, 1} for the language accepting strings containing exactly two ‘0’.

Solution:

The given question provides the following language (L) and DFA diagram

L={00, 100, 001, 1010, 0101, 11100,…….}

 

Solved example number 22 of DFA

DFA Example 23

Design a DFA with sigma ∑ = {0, 1} for the language accepting strings containing at least two ‘0’.

Solution:

The given question provides the following language (L) and DFA diagram

L={00,001,000,0011,0010,0001,0000,1100, 1001…..}

Solved example number 23 of DFA

 

DFA Example 24

Draw a DFA with sigma ∑ = {0, 1} for the language accepting strings containing at most two ‘0’.

Solution:

The given question provides the following language (L) and DFA diagram

L={0,1,10,01,001,1001,1011,1101, …..}

 

Solved example number 24 of DFA

DFA Example 25

Construct a DFA with sigma ∑ = {0, 1} for the language accepting strings starting and ending with ‘0’ always.

Solution:

The given question provides the following language (L) and DFA diagram

L={0,00,010,000, 0110, 0100…..}

Solved example number 25 of DFA

DFA Example 26

Design a DFA with sigma ∑ = {0, 1} for the language accepting strings starting and ending with different characters.

Solution:

The given question provides the following language (L) and DFA diagram

L={01,10,011,100,…..}

 

Solved example number 26 of DFA

DFA Example 27

Construct a DFA with sigma ∑ = {0, 1} for the language accepting strings starting and ending with the same characters.

Solution:

The given question provides the following language (L) and DFA diagram

L={00,11,101,010,…..}

Solved example number 27 of DFA

DFA Example 28

Design a DFA with sigma ∑ = {0, 1} for the language accepting strings containing an odd number of total zeros (or odd binary numbers strings).

Solution:

The given question provides the following language (L) and DFA diagram

L={0,01,10, 101, 010, 1011, 1110,…..}

 

Solved example number 28 of DFA

 

DFA Example 29

Construct a DFA with sigma ∑ = {0, 1} for the language accepting strings starting with ‘00’ or ’11’

Solution:

The given question provides the following language (L) and DFA diagram

L={00,11,000,111, 110,0001,0010, …..}

 

Solved example number 30 of DFA

DFA Example 30

Construct a DFA with sigma ∑ = {0, 1} for the language accepting strings ending with ‘0011’.

Solution:

The given question provides the following language (L) and DFA diagram

L={0011,00011,10011,110011,000011,…..}

 

Solved example number 31 of DFA

DFA Example 31

Construct a DFA with sigma ∑ = {0, 1} for the language accepting strings ending with ‘0110’ .

Solution:

The given question provides the following language (L) and DFA diagram

L={0110,10110,00110,110110,000110,…..}

 

Solved example number 32 of DFA

DFA Example 32

Construct a DFA with sigma ∑ = {0, 1} for the language accepting strings ending with ‘00’.

Solution:

The given question provides the following language (L) and DFA diagram

L={00,000,0100,01100,01000…..}

 

Solved example number 33 of DFA

Example:33

Design a DFA with sigma ∑ = {a, b}, accepts those strings that have an even number of “0’s” and an even number of “1’s”.

Solution:

The given question provides the following language

L= { ε, 00, 11, 0101, 1001, 0011, 00001111, 11110000,…., }

Note: Epsilon (ε) represents zero, which is even.

Let’s draw the DFA which accepts all the strings of the above language

Examples of DFA (5)

In Above DFA,

  • If state q1 becomes final instead of q0, DFA will accept all those strings with Odd “0” and even “1”.
  • And if state q2 becomes final instead of q0, then DFA will accept all those strings with even “0” and odd “1”.
  • And If state q3 becomes final instead of q0, then DFA will accept all those strings with odd “0” and odd “1”.

 

Examples of DFA for Even Odd problem to solution of a string