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?

This question was previously asked in

GATE CS 2011 Official Paper

Option 1 :

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_{0 }= {p,q,r} P_{1 }={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_{1} and P_{0}. But state r go to the only P_{0}. Hence state ' r ' is a different set.

P_{0 }={p,q} P_{1} ={r} P_{2} ={s,t}

Here state p and state q are different p goes to only P_{0} 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.