Examples of DFA

This lecture discusses more than 50 examples of DFA. But you make sure that you have already covered the topic of Deterministic Finite Automata. There are six different categories selected for examples of DFA.

Let’s explain all examples of DFA in the sequence of the given categories in the TOC. 

Category 1:  Accept Only the Given Input

 DFA accepts only one specific input string and rejects all others. For Examples

• Accepts only abbbbccc
• Accepts only 011010010
• Accepts only 101010

DFA Example: 1.1

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

Solution:

In the above example

• Regular Expression = 10
• Language of Accepted Strings = {10}
• Some Rejected Strings = {ε, 0, 1, 11, 00, 101, 100, 110}

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

Note: q3 is a dead state, at q3, for inputs “0” and “1”, it’s a self-loop.

In the above DFA, 5 tuples of DFA are given below

• States: {q0, q1, q2,q3} refers to the set of states
• Input Alphabet: {0,1} refers to the set of input alphabets
• Transition Function (δ): refers to the transition function, which is defined as
  • δ (q0, 0) = q3
  • δ (q0, 1) = q1
  • δ (q1, 0) = q2
  • δ (q1, 1) = q3
  • δ (q2, 0) = q3
  • δ (q2, 1) = q3
  • δ (q3, 0) = q3
  • δ (q3, 1) = q3
• Initial State: q0 refers to the initial state
• Final State: {q2} refers to the set of final states

Note: q3 is a dead state.

Transition Table

Transition Table for the above Deterministic Finite Automata (DFA) is

States	0	1
→ q0	q3	q1
q1	q2	q3
*q2	q3	q3
q3	q3	q3

DFA Example: 1.2

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

Solution:

The given question provides the following

• Regular Expression = aaab
• Language of Accepted Strings = {aaab}
• Some Rejected Strings = {ε, a, ab, aaa, aab, aaabb, baab, abab}

The following diagram represents the DFA that accepts only the input “aaab”.

 

Dead State aslo known as trap state

DFA Description

• States = {q0, q1, q2, q3, q4, q5}

• Input Alphabet = {a, b}

• Initial State = q0

• Final State = {q4}

 

• Transition Function δ is defined as:

  • δ(q0, a) = q1

  • δ(q0, b) = q5

  • δ(q1, a) = q5

  • δ(q1, b) = q2

  • δ(q2, a) = q5

  • δ(q2, b) = q3

  • δ(q3, a) = q5

  • δ(q3, b) = q4

  • δ(q4, a) = q5

  • δ(q4, b) = q5

  • δ(q5, a) = q5

  • δ(q5, b) = q5

Dead State = q5 (trap state)

Transition Table

Category 2:  Starts and Ends With

DFA accepts strings that start with a specific substring and/or end with a specific substring. For Examples

• Starts with 01
• Ends with 000
• Starts with a, ends with bb
• Starts and ends with the same symbol

DFA Example: 2.1

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

Solution:

The given question provides the following

• Regular Expression = 0(0+1)*
• Language of Accepted Strings = {0, 01, 00, 010, 011, 000, 001,…, }
• Some Rejected Strings = {ε, 1, 11, 101, 1001, 110}

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

DFA Description

• States = {q0, q1, q∅ }

• Input Alphabet = {0, 1}

• Initial State = q0

• Final States = {q1}

• Dead State = q∅  (trap state)

• Transition Function δ is defined as:

  • δ(q0, 0) = q1

  • δ(q0, 1) = q∅

  • δ(q1, 0) = q1

  • δ(q1, 1) = q1

  • δ(q∅ , 0) = q∅

  • δ(q∅ , 1) = q∅

Transition Table

DFA Example: 2.2

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

Solution:

The given question provides the following

• Regular Expression = 01(0+1)*
• Language of Accepted Strings = {01, 010, 011, 0100, 0111, 01101, …}
• Some Rejected Strings = {ε, 0, 1, 10, 00, 11, 001, 101}

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

DFA Description

• States = {q0, q1, q2, q3}

• Input Alphabet = {0, 1}

• Initial State = q0

• Final States = {q2}

• Dead State = q3

• Transition Function δ is defined as:

  • δ(q0, 0) = q1

  • δ(q0, 1) = q3

  • δ(q1, 0) = q3

  • δ(q1, 1) = q2

  • δ(q2, 0) = q2

  • δ(q2, 1) = q2

  • δ(q3, 0) = q3

  • δ(q3, 1) = q3

Transition Table

DFA Example: 2.3

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

Solution:

The given example provides the following language

• Regular Expression = (0+1)*0
• Language of Accepted Strings = {0, 10, 110, 000, 1010, 1110, …}
• Some Rejected Strings = {ε, 1, 11, 101, 1001, 111}

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

DFA Description

• States = {q0, q1}

• Input Alphabet = {0, 1}

• Initial State = q0

• Final State = {q1}

• Transition Function δ is defined as:

  • δ(q0, 0) = q1

  • δ(q0, 1) = q0

  • δ(q1, 0) = q1

  • δ(q1, 1) = q0

Transition Table

Example: 2.4

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

Solution:

The given question provides the following language

• Regular Expression = (0+1)*10
• Language of Accepted Strings = {10, 010, 110, 0010, 1110, 1010, …}
• Some Rejected Strings = {ε, 0, 1, 11, 00, 100, 101, 111}

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

DFA Description

• States = {q0, q1, q2}

• Input Alphabet = {0, 1}

• Initial State = q0

• Final State = {q2}

• q2 is accepting only if the last two symbols are “10”

• Transition Function δ is defined as:

  • δ(q0, 0) = q0

  • δ(q0, 1) = q1

  • δ(q1, 0) = q2

  • δ(q1, 1) = q1

  • δ(q2, 0) = q0

  • δ(q2, 1) = q1

Transition Table

DFA Example: 2.5

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 

• Regular Expression (RE) = 1(0+1)*0
• Language of Accepted Strings (L) = {10, 100, 110, 1010, 1110, 10010, …}
• Some Rejected Strings (REJ_Str) = {ε, 0, 1, 11, 00, 101, 111, 010}

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

DFA Description

• States = {q0, q1, q2, q3}

• Input Alphabet = {0, 1}

• Initial State = q0

• Final State = {q2}

•  Transition Function δ is defined as:

• • δ(q0, 0) = q3

  • δ(q0, 1) = q1

  • δ(q1, 0) = q2

  • δ(q1, 1) = q1

  • δ(q2, 0) = q2

  • δ(q2, 1) = q1

  • δ(q3, 0) = q3

  • δ(q3, 1) = q3

Transition Table

DFA Example: 2.6

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

Solution:

• Regular Expression = (0+1)*(01 + 10)
• Language of Accepted Strings = {01, 10, 101, 110, 001, 1110, 1001, …}
• Some Rejected Strings = {ε, 0, 1, 00, 11, 100, 111, 1010}

The given question provides the following DFA diagram

DFA Description

• States = {q0, q1, q2, q3, q4}

• Input Alphabet = {0, 1}

• Initial State = q0

• Final States = {q2, q4}

• Transition Function δ is defined as
  • δ(q0, 0) = q1
  • δ(q0, 1) = q3
  • δ(q1, 0) = q1
  • δ(q1, 1) = q2
  • δ(q2, 0) = q4
  • δ(q2, 1) = q3
  • δ(q3, 0) = q4
  • δ(q3, 1) = q3
  • δ(q4, 0) = q1
  • δ(q4, 1) = q2

 Transition Table

DFA Example: 2.7

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 

• Regular Expression = 0(0+1)*0
• Language of Accepted Strings = {00, 010, 000, 0111110, 0010, 0101010, …}
• Some Rejected Strings = {ε, 1, 01, 10, 11, 011, 100, 101}

DFA diagram

DFA Description

• States = {q0, q1, q2, q3}

• Input Alphabet = {0, 1}

• Initial State = q0

• Final State = {q1}

• Dead State = q3

• Transition Function δ is defined as:

• • δ(q0, 0) = q1

  • δ(q0, 1) = q3

  • δ(q1, 0) = q1

  • δ(q1, 1) = q2

  • δ(q2, 0) = q1

  • δ(q2, 1) = q2

  • δ(q3, 0) = q3

  • δ(q3, 1) = q3

 Transition Table

DFA Example: 2.8

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

• Regular Expression = (0(0+1)*1) + (1(0+1)*0)
• Language of Accepted Strings = {01, 10, 001, 110, 1010, 100, 01101, …}
• Some Rejected Strings = {ε, 0, 1, 00, 11, 010, 101, 111}

DFA diagram

 

Important: I hope you have a better understanding of the DFA transition function and table. Now we can proceed without it.

DFA Example: 2.9

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

• Regular Expression = (0(0+1)*0) + (1(0+1)*1)
• Language of Accepted Strings = {00, 11, 010, 101, 0110, 1001, …}
• Some Rejected Strings = {ε, 01, 10, 001, 110, 011, 100}

DFA diagram

Note: You can consider the following Regular Expression as well

• Regular Expression = (0(0+1)*0) + (1(0+1)*1) + 0 + 1

DFA Example: 2.10

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

Solution:

The given question provides the following

• Regular Expression = (00 + 11)(0+1)*
• Language of Accepted Strings = {00, 11, 001, 110, 0000, 1111, 00101, 11010, …}
• Some Rejected Strings = {ε, 0, 1, 01, 10, 010, 101, 1001}

DFA diagram

DFA Example: 2.11

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

Solution:

The given question provides the following

• Regular Expression = (0+1)*0011
• Language of Accepted Strings = {0011, 10011, 000011, 110011, 1010011, …}
• Some Rejected Strings = {ε, 0, 1, 001, 011, 00110, 1100, 1010}

DFA diagram

DFA Example: 2.12

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

Solution:

The given question provides the following

• Regular Expression = (0+1)*0110
• Language of Accepted Strings = {0110, 10110, 0000110, 1100110, 10010110, …}
• Some Rejected Strings = {ε, 0, 1, 011, 110, 01101, 0010, 1110}

 DFA Diagram

DFA Example: 2.13

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

Solution:

The given question provides the following

• Regular Expression = (0+1)*00
• Language of Accepted Strings = {00, 100, 1100, 0100, 11100, 00100, …}
• Some Rejected Strings = {ε, 0, 1, 01, 10, 001, 101, 1001}

DFA diagram

Category 3: Contains Substring

DFA accepts strings that contain a specific substring anywhere in the string. For Examples

• Contains 101
• Contains ababa
• Contains 000

DFA Example: 3.1

Construct a DFA that accepts all the strings over ∑ {0,1} where each contains “0” and always starts with “1”.

Solution:

The given question provides the following

• Regular Expression =1*0(0+1)*
• Language of Accepted Strings = {10, 101, 100, 1001, 10011, 110, 1010, …}
• Some Rejected Strings = {ε, 0, 01, 011, 111}

DFA Diagram

DFA Example: 3.2

Construct DFA that accepts all the strings over alphabet ∑ {0,1} where each string contains “00”.

Solution:

The given question provides the following 

• Regular Expression = (0+1)*00(0+1)*
• Language of Accepted Strings = {00, 001, 100, 1100, 000, 1001, 0010, …}
• Some Rejected Strings = {ε, 0, 1, 01, 10, 11, 101, 0101}

 DFA Diagram

DFA Example: 3.3

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

Solution:

The given question provides the following 

• Regular Expression = (0+1)*000(0+1)*
• Language of Accepted Strings = {000, 1000, 0001, 10001, 0000, 110001, …}
• Some Rejected Strings = {ε, 0, 00, 1, 010, 1010, 0010, 01010}

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

DFA Example: 3.4

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

Solution:

• Regular Expression = ((1+01+001)* (ε + 0 + 00))
• Language of Accepted Strings = {ε, 0, 1, 01, 10, 001, 1001, 100100, …} (no “000” as a substring)
• Some Rejected Strings = {000, 1000, 0001, 0000, 10001, 010001}

DFA Diagram

Note: Here, q3 is a dead state

DFA Example: 3.5

Construct a DFA that accepts all the strings over the alphabet ∑ {0,1} where each string contains “101” as a substring.

Solution:

The given question provides the following 

• Regular Expression = (0+1)*101(0+1)*
• Language of Accepted Strings = {101, 0101, 1010, 1101, 00101, 10111, …}
• Some Rejected Strings = {ε, 0, 1, 10, 01, 100, 110, 1111}

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

DFA Example: 3.6

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

Solution:

• Regular Expression = (01 + 10)*
• Language of Accepted Strings = {ε, 0, 1, 01, 10, 010, 101, 0101, 1010, …} (no “00” or “11” as substrings)
• Some Rejected Strings = {00, 11, 001, 110, 0110, 1000, 111, 000}

DFA Diagram

Correction 01: q0 is also the Final State

DFA Example: 3.7

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

Solution:

• Regular Expression = (0+1)*(01 + 10)(0+1)*
• Language of Accepted Strings = {01, 10, 001, 110, 1010, 010, 1001, …} (must contain “01” or “10”)
• Some Rejected Strings = {ε, 0, 1, 00, 11, 000, 111, 0000, 1111}

DFA Diagram for ’01’ or ’10’ as a substring

DFA Example: 3.8

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

Solution:

The given question provides the following 

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

DFA diagram

DFA Example: 3.9

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

Solution:

The given question provides the following

• Regular Expression = (1)*0(1)*0(1)*
• Language of Accepted Strings = {00, 001, 010, 100, 10101, 1010, 0110, 10101, …} (exactly two 0s)
• Some Rejected Strings = {ε, 0, 1, 000, 111, 0100, 0010, 1000}

DFA Diagram

 

DFA Example: 3.10

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

Solution:

• RE = 1* + 1*01* + 1*01*01*
• Language of Accepted Strings = {ε, 1, 11, 0, 10, 01, 101, 001, 010, 100, 011, 110, …} (strings with 0, 1, or 2 zeros only)
• Some Rejected Strings = {000, 1000, 0001, 01000, 11000, 0000, 0010}

DFA diagram

DFA Example: 3.11

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:

There’s no short, clean RE for odd number of 0s, but an equivalent expression could be:

• Regular Expression = (1*01*01*)*1*0(1*01*01*)*
• Language of Accepted Strings = {0, 10, 01, 1000, 0001, 1110, 00101, …} (strings with 1, 3, 5, … zeros)
• Some Rejected Strings = {ε, 1, 11, 00, 1010, 1100, 00, 1010}

DFA Diagram

 

DFA Example: 3.12

Design a DFA for the Language (L) that accepts only the strings where every “00” is Immediately Followed by 1 over the input alphabet ∑= {0,1}

Solution:

• Valid Strings: L = { 001, 1001, 01001, … }
•  Invalid Strings: Not in L = { 00, 000, 0000, 1000, 10100011, … }

DFA

Category 4: Specific Length

DFA accepts strings of exactly n characters. For Examples

• Strings of length 3
• Binary strings of length 5
• Strings over {a, b} of length 2

DFA Example: 4.1

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

Solution:

• Regular Expression = (0+1)(0+1)
• Language of Accepted Strings = {00, 01, 10, 11} (all strings of length exactly 2)
• Some Rejected Strings = {ε, 0, 1, 000, 0110, 1011, 111, 1001}

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

DFA Example: 4.2

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

Solution:

• Regular Expression = (0+1)(0+1)(0+1)*
• Language of Accepted Strings = {00, 01, 10, 11, 000, 010, 101, 111, 1100, …} (all strings with length ≥ 2)
• Some Rejected Strings = {ε, 0, 1}

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

DFA Example: 4.3

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

Solution:

• Regular Expression = ε + (0+1) + (0+1)(0+1)
• Language of Accepted Strings = {ε, 0, 1, 00, 01, 10, 11} (all strings of length ≤ 2)
• Some Rejected Strings = {000, 1010, 111, 001, 0101}

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

 

Correction 02: Intial is also Final in this case

DFA Example: 4.4 

Design a DFA over w {a,b}* such that length of “a” is greater or equals to 2 and there is no restriction over length of b.

Solution:

The given question provides the following language:

L = { w ∈ {a, b} | number of as ≥ 2 }*

• Accept strings like:
  aa, aab, aba, baa, bababaa, bbaabb, etc.
• Reject strings like:
  Epsilon, b, ab, a, bbabbbb (zero or one a)

RE = (a + b)*a(a + b)*a(a + b)*

DFA Diagram

DFA Example: 4.5

Design a DFA over w {a,b}* such that the length of “a” must be 2 and there is no restriction over length of b.

Solution:

The given question provides the following :

• Regular Expression = b*a b*a b*
• Language of Accepted Strings = {aa, baa, aba, aab, baba, abba, bbaab, …} (strings with exactly two ‘a’s, anywhere in the string, b’s allowed anywhere and in any number)
• Some Rejected Strings = {ε, b, bb, a, aaa, abaa, baaa, ababaa, …} (less than or more than two ‘a’s)

DFA is given below

 

DFA Example: 4.6

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 

• Regular Expression = ((0+1)(0+1))*
• Language of Accepted Strings = {ε, 00, 01, 10, 11, 0000, 0101, 1100, 1111, …} (strings with even length: 0, 2, 4, …)
• Some Rejected Strings = {0, 1, 000, 011, 101, 111, 1001, 010, …} (strings with odd length)

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

DFA Example: 4.7

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

• Regular Expression = (0+1)((0+1)(0+1))*
• Language of Accepted Strings = {0, 1, 000, 010, 101, 111, 001, 10001, …} (strings with odd length: 1, 3, 5, …)
• Some Rejected Strings = {ε, 00, 01, 10, 11, 0000, 0101, 1100} (strings with even length)

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

DFA Example: 4.8

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

Solution:

• Regular Expression: No simple RE exists for this pattern, but a conceptual structure is: ((00 + 11 + (01 + 10)(01 + 10)))*
• Language of Accepted Strings: {ε, 0011, 1100, 0101, 1001, 0110, 1010, 00001111, …} (even number of 0s and even number of 1s)
• Some Rejected Strings: {0, 1, 01, 10, 000, 111, 001, 011, 110} (strings with odd number of 0s or 1s)

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

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

In Above DFA,

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

 

Category 5: Divisibility (Binary Numbers)

DFA accepts binary strings whose decimal representation is divisible by a number. For Examples

• Binary strings divisible by 2
• Divisible by 3 (mod 3)
• Divisible by 5

DFA Example 5.1

Construct a DFA that accepts the set of all strings over {0, 1} when interpreted as a binary number that is divisible by 2.

Solution:

The given question provides the following:

• Regular Expression = (0 + 1)*(0)
• Language of Accepted Strings = {0, 10, 100, 110, 1010, 1110, …} (binary strings ending in 0 → divisible by 2)
• Some Rejected Strings = {1, 11, 101, 111, 1001, 1101, …} (binary strings ending in 1 → not divisible by 2)

Explanation (Example for 1001):

Binary 1001 = Decimal 9
Since 9 ÷ 3 = 3, it is divisible by 3.
Hence, 1001 ∈ L

Binary to Decimal Table (Divisible by 3):

The following diagram represents the DFA that accepts only binary integers divisible by 3

DFA Example: 5.2

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

Solution:

A clean and exact RE for binary numbers divisible by 3 is not simple, but the regular expression equivalent is: ((1(01*0)*1)*0*)*

The given question provides the following language

• Language of Accepted Strings = {0, 11, 110, 1001, 1100, 1111, 10010, …} (binary numbers divisible by 3)
• Some Rejected Strings = {1, 10, 101, 1110, 100, 1010, 1001, 111} (binary numbers not divisible by 3)

The explanation for string 1001 is given below.

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

Binary to Decimal Table (Divisible by 3):

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

DFA Example: 5.3

Construct DFA that accepts all the strings over alphabet ∑ {0,1} where binary integers are divisible by 4

Solution:

• Regular Expression = (0+1)*00
• Language of Accepted Strings = {0, 100, 1000, 1100, 10000, 100100, …} (binary integers divisible by 4)
• Some Rejected Strings = {1, 10, 11, 101, 111, 1010, 1101, 1001} (binary integers not divisible by 4)

The given question provides the following language

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

The explanation for string 10000 is given below.

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

Binary to Decimal Table (Divisible by 4):

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

 

DFA Example: 5.4

Construct a DFA that accepts the set of all strings over {0, 1} when interpreted as a binary number, that is, divisible by 5.

Solution:

The given question provides the following language

L = { 0, 101, 1010, 1111, 10100, 11001, 11110, … }

Note: Regular Expression  is not expressible concisely with standard regular expressions (requires modulo-5 tracking via DFA)

Category 6: General DFA Examples

Let’s discuss some general examples of DFA

DFA Example: 6.1

Draw a DFA for to accept any number of “a” over the input alphabet Σ = {a}

Solution:

The given question provides the following

• Regular Expression = a*
• Language of Accepted Strings = {ε, a, aa, aaa, aaaa, …} (any number of 'a', including none)
• Some Rejected Strings = {b, ab, ba, aab, bbb} (any string containing symbols other than 'a')

DFA Diagram is

DFA Example: 6.2

Draw a DFA for the language accepting even binary number strings over the input alphabet Σ = {0,1}

Solution:

The given question provides the following

• Regular Expression = (0+1)*0
• Language of Accepted Strings = {0, 10, 100, 110, 1110, 1010, 000, …} (binary numbers ending with ‘0’, i.e., even)
• Some Rejected Strings = {1, 11, 101, 111, 1001, 1101} (binary numbers ending with ‘1’, i.e., odd)

DFA Diagram

If we convert the given binary language into decimal, we easily understand that the given numbers are even binary numbers

Binary	Decimal
0	0
10	2
100	4
110	6
1000	8
1010	10
1110	14
10000	16
so on…..	—

 

DFA Example: 6.3

Draw a DFA for the language accepting Odd binary numbers strings over the input alphabet Σ = {0,1}

Solution:

The given question provides the following 

• Regular Expression = (0+1)*1
• Language of Accepted Strings = {1, 11, 101, 111, 1001, 1101, …} (binary numbers ending in '1', i.e., odd)
• Some Rejected Strings = {ε, 0, 10, 100, 110, 1110, 1010} (binary numbers ending in '0', i.e., even)

DFA Diagram is given below

if we convert given binary language into decimal, we easily understant that given numbers are odd binary numbers

Binary	Decimal
1	1
11	3
101	5
111	7
1001	9
1011	11
1111	15
so on ….	….

DFA Example: 6.4

Draw a DFA for the language accepting Even or Odd binary numbers strings over input alphabets Σ = {0,1}

Solution:

The given question provides the following

• Regular Expression = (0+1)*
• Language of Accepted Strings = {ε, 0, 1, 10, 11, 101, 1110, 1101, …} (all binary strings)
• Some Rejected Strings = Ø (None — all strings are accepted)

DFA Diagram is

Binary to decimal conversion

DFA Example: 6.5

Draw a DFA for Language L = {a^n b | n>= 0} over input alphabets Σ = {a,b}

Solution:

The given question provides the following 

• Regular Expression = a*b
• Language of Accepted Strings = {b, ab, aab, aaab, aaaab, …}
• Some Rejected Strings = {ε, a, aa, abb, ba, bab, bb, aaa, aaba}

DFA Diagram is

DFA Example: 6.6

Draw a DFA for Language L = {0^n 1^m | m, n>= 1, (m) mode (3) = 1} over input alphabets Σ = {0,1}

Solution:

Examples in the Language L:

So,

L = { 01, 001, 0001, 01, 001111, 0001111, … }
(All strings starting with 1 or more 0s, then m 1s such that m % 3 = 1)

DFA Example: 6.7

Design a DFA such that: L ={a^n b^m | n,m = 1}

Solution:

The given question provides the following language

 L = {ab, aab, aaab, abbb, aabb, abbbb, …}