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

Deterministic Finite Automata Formal Definition

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

• Q represents a finite set of all states (q_0, q_1, q_{2,   …} q_n). 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
• q₀ represents the initial state where (q₀ ∈ 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 (q₀) is denoted by a circle with a single incoming arrow.
• Double circles denote the final state.

The following figure shows all notations of 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).

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

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).

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

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
• q₀ = {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.

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.