A deterministic finite automaton (DFA) D with alphabet ∑ = {a,b} is given below.

Which of the following finite state machines is a valid minimal DFA which accepts the same language as D?

The correct answer is option 1.

Key Points

Minimization of DFA :

Step 1:

We will divide Q (set of states) into two sets. One set will contain all final states and another set will contain non-final states.

P₀ = {p,q,r}  P₁ ={s,t}

Step 2: 

Find Pk by partitioning the different sets of Pk-1. In each set of Pk-1, we will take all possible pair of states. If two states of a set are distinguishable, we will split the sets into different sets in Pk.

Here state p and q states go to only P₁ and P₀. But state r go to the only P₀. Hence state ' r ' is a different set. 

P₀ ={p,q} P₁ ={r} P₂ ={s,t} 

Here state p and state q  are different p goes to only P₀ and P2 and q goes to only P1 and P2. So both are different.

P0 ={p} P1 ={q}  P2 ={r} P3 ={s,t}

P0 ={p} P1 ={q}  P2 ={r} P3 ={s,t}

Step 3: 

Stop when Pk = Pk-1 (No change in the partition) 

Step 4: 

All states of one set are merged into one. No. of states in minimized DFA will be equal to no. of sets in Pk. 

minimized DFA is,

Alternate Method

Option 2 and Option 3:

Minimized DFA  accepts string ' b ' but the given deterministic finite automata didn't accept the string b Hence option 2 and option 3 are false.

Option 4:

Minimized DFA  accepts string 'bba' but the given deterministic finite automata didn't accept the string 'bba' Hence option 4 is false.