Techtaleem.com logo

Examples of DFA

Deterministic Finite Automata (DFA) are a fundamental concept in automata theory and formal languages, widely used in computer science, compiler design, pattern matching, and lexical analysis. This article explains DFA with clear examples, making it easy for students and beginners to understand.

A Deterministic Finite Automaton (DFA) is a finite state machine that accepts or rejects strings of symbols by transitioning through a finite number of states.

A DFA is defined by a 5-tuple:

DFA = (Q, Σ, δ, q₀, F)

Where:

  • Q = finite set of states

  • Σ = input alphabet

  • δ = transition function (Q × Σ → Q)

  • q₀ = initial state

  • F = set of accepting (final) states

 In a DFA, for every state and input symbol, there is exactly one transition.

DFA Question Category 1:  Accept Only the Given Input

 In this section, a DFA accepts only one specific input string and rejects all other strings. For example,

  • Accepts only the string “aaab”
  • Accepts only the string “01”

DFA Example 01:Draw a DFA which accept only input string “1”
Over input alphabets ∑ = {0,1}

Examples of DFA 01

The explanation of the above DFA is given below

  • States = {q0, q1, q2}
  • Input Alphabet = {0,1}
  • Initial State = q0
  • Final State = q1
  • Dead State = q2

Transition Function (δ) for all input alphabets (“0,1”) is defined in the following DFA Transition Table

DFA Transition Table Example 01
DFA Example 02:Draw a DFA which accept only input string “a”
Over input alphabets ∑ = {a,b,c}

Example of DFA 02

The explanation of the above DFA is given below

  • States = {q0, q1, q2}
  • Input Alphabet = {a,b,c}
  • Initial State = q0
  • Final State = q1
  • Dead State = q2

Transition Function (δ) for all input alphabets (“a,b,c”) is defined in the following DFA Transition Table

DFA Transition Table Example 02
DFA Example 03:Draw a DFA which accept only input string “b”
Over input alphabets ∑ = {a,b,c,d}

Example of DFA 03

The explanation of the above DFA is given below

  • States = {q0, q1, q2}
  • Input Alphabet = {a,b,c,d}
  • Initial State = q0
  • Final State = q1
  • Dead State = q2

Transition Function (δ) for all input alphabets (“a,b,c,d”) is defined in the following DFA Transition Table

DFA Transition Table Example 03

DFA Example 04:Draw a DFA which accept only input string “10”
Over input alphabets ∑ = {0,1}

Example of DFA 04

The explanation of the above DFA is given below

  • States = {q0, q1, q2,q3}
  • Input Alphabet = {0,1}
  • Initial State = q0
  • Final State = q2
  • Dead State = q3

Transition Function (δ) for all input alphabets (“0,1”) is defined in the following DFA Transition Table

DFA Transition Table Example 04

DFA Example  05:Draw a DFA which accept only input string “bc”
Over input alphabets ∑ = {a,b,c}

Examples of DFA 05

The explanation of the above DFA is given below

  • States = {q0, q1, q2,q3}
  • Input Alphabet = {a,b,c}
  • Initial State = q0
  • Final State = q2
  • Dead State = q3

Transition Function (δ) for all input alphabets (“a,b,c”) is defined in the following DFA Transition Table

DFA Transition Table Example 05

DFA Example 06:Draw a DFA which accept only input string “abcd”
Over input alphabets ∑ = {a,b,c,d,e}

Examples of DFA 06

The explanation of the above DFA is given below

  • States = {q0, q1, q2,q3,q4,q5}
  • Input Alphabet = {a,b,c,d,e}
  • Initial State = q0
  • Final State = q4
  • Dead State = q5

Transition Function (δ) for all input alphabets (“a,b,c,d,e”) is defined in the following DFA Transition Table

DFA Transition Table Example 06

DFA Example 07:Draw a DFA which accept only input string “11001”
Over input alphabets ∑ = {0,1}

Example of DFA 07

The explanation of the above DFA is given below

  • States = {q0, q1, q2,q3,q4,q5,q6}
  • Input Alphabet = {0,1}
  • Initial State = q0
  • Final State = q5
  • Dead State = q6

Transition Function (δ) for all input alphabets (“0,1”) is defined in the following DFA Transition Table

DFA Transition Table Example 07

DFA Example 08: Draw a DFA which accept only input string “abacba”
Over input alphabets ∑ = {a,b,c}

Example of DFA 08

The explanation of the above DFA is given below

  • States = {q0, q1, q2,q3,q4,q5,q6,q7}
  • Input Alphabet = {a,b,c}
  • Initial State = q0
  • Final State = q6
  • Dead State = q7

Transition Function (δ) for all input alphabets (“a,b,c”) is defined in the following DFA Transition Table

DFA Transition Table Example 08

DFA Example 09:

Example Of DFA 01Example Of DFA 01

The explanation of the above DFA is given below

  • States = {q0, q1, q2, q3, q4, q5}
  • Input Alphabet = {0,1}
  • Initial State = q0
  • Final State = q4
  • Dead State = q5

DFA Example: 02

Example Of DFA 02

The explanation of the above DFA is given below

  • States = {q0, q1, q2, q3,}
  • Input Alphabet = {1,0}
  • Initial State = q0
  • Final State = q2
  • Dead State = q3

DFA Example: 03

Example Of DFA 03

The explanation of the above DFA is given below

  • States = {q0, q1, q2, q3, q4,}
  • Input Alphabet = {0,1}
  • Initial State = q0
  • Final State = q3
  • Dead State = q4

DFA Example: 04 (start with)

Example Of DFA 04

The explanation of the above DFA is given below

  • States = {q0, q1, q2}
  • Input Alphabet = {1,0}
  • Initial State = q0
  • Final State = q1
  • Dead State = q2

DFA Example: 05 (similar to 3)

Example Of DFA 05

The explanation of the above DFA is given below

  • States = {q0, q1, q2, q3, q4}
  • Input Alphabet = {1,0}
  • Initial State = q0
  • Final State = q3
  • Dead State = q4

DFA Example: 06 (similar to 2)

Example Of DFA 06

The explanation of the above DFA is given below

  • States = {q0, q1, q2, q3}
  • Input Alphabet = {1,0}
  • Initial State = q0
  • Final State = q2
  • Dead State = q3

DFA Example: 07

Example Of DFA 07

The explanation of the above DFA is given below

  • States = {q0, q1, q2, q3, q4, q5}
  • Input Alphabet = {1,0}
  • Initial State = q0
  • Final State = q4
  • Dead State = q5

DFA Example: 08

Example Of DFA 08

The explanation of the above DFA is given below

  • States = {q0, q1, q2, q3, q4, q5}
  • Input Alphabet = {0,1}
  • Initial State = q0
  • Final State = q4
  • Dead State = q5

DFA Example: 09

Example Of DFA 09

The explanation of the above DFA is given below

  • States = {q0, q1, q2, q3, q4, q5}
  • Input Alphabet = {0,1}
  • Initial State = q0
  • Final State = q4
  • Dead State = q5

DFA Example: 10

Example Of DFA 10

The explanation of the above DFA is given below

  • States = {q0, q1, q2, q3}
  • Input Alphabet = {1,0}
  • Initial State = q0
  • Final State = q2
  • Dead State = q3

DFA Example: 11

Example Of DFA 11

The explanation of the above DFA is given below

  • States = {q0, q1, q2, q3}
  • Input Alphabet = {0,1}
  • Initial State = q0
  • Final State = q2
  • Dead State = q3

DFA Example: 12

Example Of DFA 12

The explanation of the above DFA is given below

  • States = {q0, q1, q2, q3, q4, q5}
  • Input Alphabet = {1,0}
  • Initial State = q0
  • Final State = q4
  • Dead State = q5

DFA Example: 13

Example Of DFA 13

The explanation of the above DFA is given below

  • States = {q0, q1, q2, q3, q4, q5}
  • Input Alphabet = {1,0}
  • Initial State = q0
  • Final State = q4
  • Dead State = q5

DFA Example: 14

Example Of DFA 14

The explanation of the above DFA is given below

  • States = {q0, q1}
  • Input Alphabet = {0,1}
  • Initial State = q0
  • Final State = q1

DFA Example: 15

Example Of DFA 15

The explanation of the above DFA is given below

  • States = {q0, q1, q2, q3}
  • Input Alphabet = {1,0}
  • Initial State = q0
  • Final State = q4
  • Dead State = q3

DFA Example: 16

Example Of DFA 16

The explanation of the above DFA is given below

  • States = {q0, q1, q2, q3, q4, q5}
  • Input Alphabet = {a,b}
  • Initial State = q0
  • Final State = q4
  • Dead State = q5

DFA Example: 17

Example Of DFA 17

The explanation of the above DFA is given below

  • States = {q0, q1, q2, q3}
  • Input Alphabet = {a,b}
  • Initial State = q0
  • Final State = q2
  • Dead State = q3

DFA Example: 18

Example Of DFA 18

The explanation of the above DFA is given below

  • States = {q0, q1, q2, q3}
  • Input Alphabet = {b,a}
  • Initial State = q0
  • Final State = q2
  • Dead State = q3

DFA Example: 19

Example Of DFA 19

The explanation of the above DFA is given below

  • States = {q0, q1, q2, q3, q4}
  • Input Alphabet = {b,a}
  • Initial State = q0
  • Final State = q3
  • Dead State = q4

DFA Example: 20

Example Of DFA 14Example Of DFA 20

The explanation of the above DFA is given below

  • States = {q0, q1, q2}
  • Input Alphabet = {0,1}
  • Initial State = q0
  • Final State = q2

"Your Support, Our Priority"

"We Make It Easy"