Tech Taleem Logo

DFA in TOC

DFA in TOC stand for Deterministic Finite Automata. DFA is a type of finite state that is used to regular languages and the regular language can be finite or infinite set of strings. It is a key concept or most important topic in theory of automata. A Deterministic Finite Automata (DFA) is a defined by 5-tuple (Q,Σ,δ,q0,F). These five tuples are as follow.

DFA = (Q,Σ,δ,q0,F)

  • Q is a finite and non-empty set of states.

Example: Q = {q0, q1, q2}

  • Σ is a finite non-empty set of finite input alphabet.

Example: Σ = {a, b} for alphabet strings.

Example: Σ = {0, 1} for binary strings.

  • δ is a transition function that tells us how DFA moves from one state to another based on input.

Example: δ (q0, 0)

Formula: δ: Q × Σ → Q
  • q0 is the initial state and the initial state are always one.

Example: q0 is the initial state where the DFA start.

Note: q0 ∈ Q
  • F is the set of finite final state.

Example: F = {q2}

Note: F ⊆ Q

Deterministic Finite Automata Construction Examples

Hare are 20 examples of DFA are as given.

Deterministic Finite Automata: Example 01

Draw a DFA which accept only input string “a”
Over input alphabets Σ = {a,b,c}

DFA Example 01

At State q0

  • For Input a: Transition goes to q1.
  • For Input b: Transition goes to q2.
  • For Input c: Transition goes to q2.

At State q1

  • For Input a: Transition goes to q2.
  • For Input b: Transition goes to q2.
  • For Input c: Transition goes to q2.

At State q2

  • For Input a: Transition goes to q2.
  • For Input b: Transition goes to q2.
  • For Input c: Transition goes to q2.

Deterministic Finite Automata: Example 02

Draw a DFA which accept only input string “b”
Over input alphabets Σ = {a,b,c,d}

DFA Example 02

At State q0

  • For Input b: Transition goes to q1.
  • For Input a: Transition goes to q2.
  • For Input c: Transition goes to q2.
  • For Input d: Transition goes to q2.

At State q1

  • For Input a: Transition goes to q2.
  • For Input b: Transition goes to q2.
  • For Input c: Transition goes to q2.
  • For Input d: Transition goes to q2.

At State q2

  • For Input a: Transition goes to q2.
  • For Input b: Transition goes to q2.
  • For Input c: Transition goes to q2.
  • For Input d: Transition goes to q2.

Deterministic Finite Automata: Example 03

Draw a DFA which accept only input string “c”
Over input alphabets Σ = {a,b,c,d}

DFA Example 03

At State q0

  • For Input c: Transition goes to q1.
  • For Input a: Transition goes to q2.
  • For Input b: Transition goes to q2.
  • For Input d: Transition goes to q2.

At State q1

  • For Input a: Transition goes to q2.
  • For Input b: Transition goes to q2.
  • For Input c: Transition goes to q2.
  • For Input d: Transition goes to q2.

At State q2

  • For Input a: Transition goes to q2.
  • For Input b: Transition goes to q2.
  • For Input c: Transition goes to q2.
  • For Input d: Transition goes to q2.

Deterministic Finite Automata: Example 04

Draw a DFA which accept only input string “1”
Over input alphabets Σ = {0,1}

DFA Example 04

At State q0

  • For Input 1: Transition goes to q1.
  • For Input 0: Transition goes to q2.

At State q1

  • For Input 0: Transition goes to q2.
  • For Input 1: Transition goes to q2.

At State q2

  • For Input 0: Transition goes to q2.
  • For Input 1: Transition goes to q2.

Deterministic Finite Automata: Example 05

Draw a DFA which accept only input string “10”
Over input alphabets Σ = {0,1}

DFA Example 05

At State q0

  • For Input 1: Transition goes to q1.
  • For Input 0: Transition goes to q3.

At State q1

  • For Input 0: Transition goes to q2.
  • For Input 1: Transition goes to q3.

At State q2

  • For Input 0: Transition goes to q3.
  • For Input 1: Transition goes to q3.

At State q3

  • For Input 0: Transition goes to q3.
  • For Input 1: Transition goes to q3.

Deterministic Finite Automata: Example 06

Draw a DFA which accept only input string “1110”
Over input alphabets Σ = {0,1}

DFA Example 06

At State q0

  • For Input 1: Transition goes to q1.
  • For Input 0: Transition goes to q5.

At State q1

  • For Input 1: Transition goes to q2.
  • For Input 0: Transition goes to q5.

At State q2

  • For Input 1: Transition goes to q3.
  • For Input 0: Transition goes to q5.

At State q3

  • For Input 0: Transition goes to q4.
  • For Input 1: Transition goes to q5.

At State q4

  • For Input 0: Transition goes to q5.
  • For Input 1: Transition goes to q5.

At State q5

  • For Input 0: Transition goes to q5.
  • For Input 1: Transition goes to q5.

Deterministic Finite Automata: Example 07

Draw a DFA which accept only input string “bc”
Over input alphabets Σ = {a,b,c}

DFA Example 07

At State q0

  • For Input b: Transition goes to q1.
  • For Input a: Transition goes to q3.
  • For Input c: Transition goes to q3.

At State q1

  • For Input c: Transition goes to q2.
  • For Input a: Transition goes to q3.
  • For Input b: Transition goes to q3.

At State q2

  • For Input a: Transition goes to q3.
  • For Input b: Transition goes to q3.
  • For Input c: Transition goes to q3.

At State q3

  • For Input a: Transition goes to q3.
  • For Input b: Transition goes to q3.
  • For Input c: Transition goes to q3.

Deterministic Finite Automata: Example 08

Draw a DFA which accept only input string “ab”
Over input alphabets Σ = {a,b}

DFA Example 08

At State q0

  • For Input a: Transition goes to q1.
  • For Input b: Transition goes to q3.

At State q1

  • For Input b: Transition goes to q2.
  • For Input a: Transition goes to q3.

At State q2

  • For Input a: Transition goes to q3.
  • For Input b: Transition goes to q3.

At State q3

  • For Input a: Transition goes to q3.
  • For Input b: Transition goes to q3.

Deterministic Finite Automata: Example 09

Draw a DFA which accept only input string “abb”
Over input alphabets Σ = {a,b}

DFA Example 09

At State q0

  • For Input a: Transition goes to q1.
  • For Input b: Transition goes to q4.

At State q1

  • For Input b: Transition goes to q2.
  • For Input a: Transition goes to q4.

At State q2

  • For Input b: Transition goes to q3.
  • For Input a: Transition goes to q4.

At State q3

  • For Input a: Transition goes to q4.
  • For Input b: Transition goes to q4.

At State q4

  • For Input a: Transition goes to q4.
  • For Input b: Transition goes to q4.

Deterministic Finite Automata: Example 10

Draw a DFA which accept only input string “1010”
Over input alphabets Σ = {0,1}

DFA Example 10

At State q0

  • For Input 1: Transition goes to q1.
  • For Input 0: Transition goes to q5.

At State q1

  • For Input 0: Transition goes to q2.
  • For Input 1: Transition goes to q5.

At State q2

  • For Input 0: Transition goes to q5.
  • For Input 1: Transition goes to q3.

At State q3

  • For Input 0: Transition goes to q4.
  • For Input 1: Transition goes to q5.

At State q4

  • For Input 0: Transition goes to q5.
  • For Input 1: Transition goes to q5.

At State q5

  • For Input 0: Transition goes to q5.
  • For Input 1: Transition goes to q5.

Deterministic Finite Automata: Example 11

Draw a DFA which accept only input string “0101”
Over input alphabets Σ = {0,1}

DFA Example 11

At State q0

  • For Input 0: Transition goes to q1.
  • For Input 1: Transition goes to q5.

At State q1

  • For Input 1: Transition goes to q2.
  • For Input 0: Transition goes to q5.

At State q2

  • For Input 0: Transition goes to q3.
  • For Input 1: Transition goes to q5.

At State q3

  • For Input 0: Transition goes to q5.
  • For Input 1: Transition goes to q4.

At State q4

  • For Input 0: Transition goes to q5.
  • For Input 1: Transition goes to q5.

At State q5

  • For Input 0: Transition goes to q5.
  • For Input 1: Transition goes to q5.

Deterministic Finite Automata: Example 12

Draw a DFA which accept only input string “11101”
Over input alphabets Σ = {0,1}

DFA Example 12

At State q0

  • For Input 1: Transition goes to q1.
  • For Input 0: Transition goes to q6.

At State q1

  • For Input 1: Transition goes to q2.
  • For Input 0: Transition goes to q6.

At State q2

  • For Input 1: Transition goes to q3.
  • For Input 0: Transition goes to q6.

At State q3

  • For Input 0: Transition goes to q4.
  • For Input 1: Transition goes to q6.

At State q4

  • For Input 0: Transition goes to q6.
  • For Input 1: Transition goes to q5.

At State q5

  • For Input 0: Transition goes to q6.
  • For Input 1: Transition goes to q6.

At State q6

  • For Input 0: Transition goes to q6.
  • For Input 1: Transition goes to q6.

Deterministic Finite Automata: Example 13

Draw a DFA which accept only input string “a(a+b)*”
Over input alphabets Σ = {a,b}

DFA Example 13

At State q0

  • For Input a: Transition goes to q1.
  • For Input b: Transition goes to q2.

At State q1

  • For Input a: Transition goes to q1.
  • For Input b: Transition goes to q1.

At State q2

  • For Input a: Transition goes to q2.
  • For Input b: Transition goes to q2.

Deterministic Finite Automata: Example 14

Draw a DFA which accept only input string “b(b+a)*”
Over input alphabets Σ = {a,b}

DFA Example 14

At State q0

  • For Input b: Transition goes to q1.
  • For Input a: Transition goes to q2.

At State q1

  • For Input a: Transition goes to q1.
  • For Input b: Transition goes to q1.

At State q2

  • For Input a: Transition goes to q2.
  • For Input b: Transition goes to q2.

Deterministic Finite Automata: Example 15

Draw a DFA which accept only input string “a(a+b)*a”
Over input alphabets Σ = {a,b}

DFA Example 15

At State q0

  • For Input a: Transition goes to q1.
  • For Input b: Transition goes to q3.

At State q1

  • For Input a: Transition goes to q1.
  • For Input b: Transition goes to q2.

At State q2

  • For Input a: Transition goes to q1.
  • For Input b: Transition goes to q2.

At State q3

  • For Input a: Transition goes to q3.
  • For Input b: Transition goes to q3.

Deterministic Finite Automata: Example 16

Draw a DFA which accept only input string “1(1+0)*”
Over input alphabets Σ = {0,1}

DFA Example 16

At State q0

  • For Input 1: Transition goes to q1.
  • For Input 0: Transition goes to q2.

At State q1

  • For Input 1: Transition goes to q1.
  • For Input 0: Transition goes to q1.

At State q2

  • For Input 1: Transition goes to q2.
  • For Input 0: Transition goes to q2.

Deterministic Finite Automata: Example 17

Draw a DFA which accept only input string “0(0+1)*”
Over input alphabets Σ = {0,1}

DFA Example 17

At State q0

  • For Input 0: Transition goes to q1.
  • For Input 1: Transition goes to q2.

At State q1

  • For Input 0: Transition goes to q2.
  • For Input 1: Transition goes to q2.

At State q2

  • For Input 0: Transition goes to q2.
  • For Input 1: Transition goes to q2.

Deterministic Finite Automata: Example 18

Draw a DFA which accept only input string “1(1+0)*1”
Over input alphabets Σ = {0,1}

DFA Example 18

At State q0

  • For Input 1: Transition goes to q1.
  • For Input 0: Transition goes to q3.

At State q1

  • For Input 1: Transition goes to q1.
  • For Input 0: Transition goes to q2.

At State q2

  • For Input 0: Transition goes to q2.
  • For Input 1: Transition goes to q1.

At State q3

  • For Input 0: Transition goes to q3.
  • For Input 1: Transition goes to q3.

Deterministic Finite Automata: Example 19

Draw a DFA which accept only input string “abacba”
Over input alphabets Σ = {a,b,c}

DFA Example 19

At State q0

  • For Input a: Transition goes to q1.
  • For Input b: Transition goes to q7.
  • For Input c: Transition goes to q7.

At State q1

  • For Input b: Transition goes to q2.
  • For Input c: Transition goes to q2.
  • For Input a: Transition goes to q7.

At State q2

  • For Input a: Transition goes to q3.
  • For Input b: Transition goes to q7.
  • For Input c: Transition goes to q7.

At State q3

  • For Input c: Transition goes to q4.
  • For Input a: Transition goes to q7.
  • For Input b: Transition goes to q7.

At State q4

  • For Input b: Transition goes to q5.
  • For Input a: Transition goes to q7.
  • For Input c: Transition goes to q7.

At State q5

  • For Input a: Transition goes to q6.
  • For Input b: Transition goes to q7.
  • For Input c: Transition goes to q7.

At State q6

  • For Input a: Transition goes to q7.
  • For Input b: Transition goes to q7.
  • For Input c: Transition goes to q7.

At State q7

  • For Input a: Transition goes to q7.
  • For Input b: Transition goes to q7.
  • For Input c: Transition goes to q7.

Deterministic Finite Automata: Example 20

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

DFA Example 20

At State q0

  • For Input a: Transition goes to q1.
  • For Input b: Transition goes to q5.
  • For Input c: Transition goes to q5.
  • For Input d: Transition goes to q5.
  • For Input e: Transition goes to q5.

At State q1

  • For Input b: Transition goes to q2.
  • For Input a: Transition goes to q5.
  • For Input c: Transition goes to q5.
  • For Input d: Transition goes to q5.
  • For Input e: Transition goes to q5.

At State q2

  • For Input c: Transition goes to q3.
  • For Input a: Transition goes to q5.
  • For Input b: Transition goes to q5.
  • For Input d: Transition goes to q5.
  • For Input e: Transition goes to q5.

At State q3

  • For Input d: Transition goes to q4.
  • For Input a: Transition goes to q5.
  • For Input b: Transition goes to q5.
  • For Input c: Transition goes to q5.
  • For Input e: Transition goes to q5.

At State q4

  • For Input a: Transition goes to q5.
  • For Input b: Transition goes to q5.
  • For Input c: Transition goes to q5.
  • For Input d: Transition goes to q5.
  • For Input e: Transition goes to q5.

At State q5

  • For Input a: Transition goes to q5.
  • For Input b: Transition goes to q5.
  • For Input c: Transition goes to q5.
  • For Input d: Transition goes to q5.
  • For Input e: Transition goes to q5.

"Your Support, Our Priority"

"We Make It Easy"