Deterministic Finite Automata (DFA)

The finite automata are also called deterministic finite automata or automaton, where Deterministic means uniqueness of the computation.

  • DFA accepts all finite regular languages and some infinite regular languages as well.
  • For each sigma value (0, 1…n), each state must provide a path.
  • DFA cannot move to another state without any input character, so a Null move is not accepted.
  • DFA may have multiple final states.

The following is a simple example of DFA Simple Example Of DFA

Deterministic Finite Automata Formal Definition

The following 5 tuples (Q, ∑, δ, q0, F) represent the deterministic finite automata more effectively,

  • Q represents a finite set of all states (q0, q1, q2,   … qn). where n is a finite number
  • representing a finite set of symbols or alphabets. i.e. {0, 1,a,b},
  • δ represents a transition function where δ: Q × ∑ → Q
  • q0 represents the initial state where (q0 ∈ Q).
  • F represents a set of final states/states where F will be a subset ( ⊆ ) of Q.

Notations in Deterministic Finite Automata

The following are the notations of deterministic finite automata

  • The vertices represent the states.
  • The arrow labeled with an input alphabet () shows the transitions (δ).
  • The initial state (q0) is denoted by a circle with a single incoming arrow.
  • Double circles denote the final state.

The following figure shows all notations of DFA

Graphical Representation of a DFA

DFA Construction Understanding

Suppose we are going to construct a DFA that accepts a language of all strings that ends with “a” over sigma (∑) = {a, b}. Then,

Step 1: Let’s drive all possible strings of a given language 

L= {a, aa, ba, aaa, bba, aba, aaaa, ……….}

Step 2: For each sigma value (0, 1…n), there must be a provided path from each state (q0, q1, q2….qn).

Possibilities of a path for each input from any state

  • May Go to next state if exist
  • Self-loop
  • Go to the trap state
  • May Go to the previous state if exists

Step 3: Now Draw the Automata model, which will always be according to the generated language. Automata machine must accept the strings of a given language (i.e., minimum to maximum string).

Deterministic Finite Automata Construction

Let construct DFA for language L= {a, aa, ba, aaa, bba, aba, aaaa, ……….}

Step 01: As the Minimum length string is “a”, which will be accepted as

Construction of deterministic finite automata Step 1

Step 02: At the initial state (q0), the path for input “a” is provided.  There must be a path for input “b” from an initial state (q0).

deterministic finite automata step 2

Step 03: In the same way, q1 must tell the path against each input value of sigma “a” and “b”.  So, the final DFA, which will accept all the strings of the given language, is given below

Construction of deterministic finite automata Step 3

5-Tuples of Deterministic Finite Automata 

When DFA is constructed, we can explain its 5-tuples easily. As the above DFA is explained below with 5-tuples

  • Q = {q0, q1}   //states will be q0 and q1
  • ∑ = {a, b}      // input already given in question
  • q0 = {q0}        // start state is q0
  • F = {q1}        // final state will become q1
  • Transition function δ (δ: Q × ∑ → Q) as shown by the following table

As q0,q1 are states and a,b are input values of Sigma. Following is the DFA transition table.

Current State Next State for Input “a” Next State for Input “b”
q0 q1 q0
q1 q1 q0

Don’t Confuse

  • If state names are a,b,c,d….z, then  sigma values will be 0,1,2,3…n
  • If state names are q0, q1, q2, q3…qn, then sigma values can be a,b,c…z or 0,1,2,3…n

Note: state and sigma values cannot be the same in notation.