GATE CSE 2011 | Question: 45

Question

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

Which of the following finite state machines is a valid minimal $\text{DFA}$ which accepts the same languages as $D$?

• A.
  
• B.
  
• C.
  
• D.
  

Comments

i applied DFA minimization algorithm and found minimized DFA has {r},{P},{Q},{S,T} states

also, with observation only, we can see that behaviour of states S and T is same

option C and D are eliminated because we need 4 states in minimal DFA

in option B, S is not final but in original DFA it is final

only option left with is A.

---

but do we ignore dead state everytime when we are minimizing dfa?

---

$I$ $solved$ $it$ $without$ $using$ $pen$
$observation$ - $In$ $the$ $given$ $DFA,$ $the$ $string$ $b$ $is$ $not$ $accepted.$ $However,$ $in$ $options$ $B,$ $C,$ $and$ $D,$ $the$ $string$ $b$ $is$ $accepted.$ $Therefore,$ $these$ $options$ $cannot$ $be$ $equivalent$ $to$ $the$ $given$ $DFA.$

Answer 1

Correct Option: A

In (B) and (C) when the first letter of input is '$b$' we reach final state, while in the given DFA first letter '$b$' is not a final state. So, (B) and (C) are not accepting same language as the given DFA.

In (D) we can reach final state when the last letter is '$a$', whatever be the previous transitions. But in the given DFA, when the first $2$ letters are '$b$' we can never reach the final state. So, (D) is also accepting a different language than the given DFA.

Comments

@Arjun Suresh Sir is there any more counterexample for option D?

---

@Sandeep Suri, 

on state Q, given FA is going to dead state but in option D it's looping on state Q.

RE for option D = (a + b⁺a) (a+ b)*

for option A = (a + ba)(a+b)*

---

Another quick way to see why option B, C and D fail, is all of them accepts input string ‘b’. However, the original DFA does not.

Answer 2

Minimization using set of equivalent states

First set of equivalent states 

$\pi$₀ ={ I,II}        I={p,q,r} set of non-final state        II = {s,t} set of final state 

now check states in set I are equivalents or not 

p x a -> s [II , goes to state that is in set II]                q x a -> t [II]                        r x a -> r [I]

p x b -> q [I]                                                           q x b -> r [I]                        r x b -> r[I]

it is clear p,q are equivalent (both states on symbol a goes to states that is in set II , both states on symbol  b goes to states that is in set I) but r behaves differently, set {p,q,r} divides into two set {p,q},{r}

now check states in set II are equivalent or not

s x a -> s[II]                               t x a -> t [II]

s x b -> s[II]                               t x a ->t [II]

so s,t are equivalent states 

that results in 

Second set of equivalent states 

$\pi$₁ ={ I,II,III}        I = {p,q}    II =  {r}     III = {s,t} 

check all states in I are equivalents or not  , same for set II and set III using same procedure as above

Third set of equivalent states 

$\pi$₂ ={ I,II,III,IV}        I = {p}    II =  {q}     III = {r}        IV = {s,t} 

further 

$\pi$₃ =$\pi$₂   .i,e that cannot be further minimized 

s and t are equivalent states 

Minimized DFA will be same as given in option A 

Answer 3

RE corresponding to our DFA is: a(a+b)* + ba(a+b)*

consider option B and C : it will accept string like simple 'b'. Hence, rejected.

Option D: it will accept string like bba which is not a part of our language.Hence, rejected.

So, option A is the right answer.

Comments

option B,C,D  accepts ‘b’ which is not accepted by given DFA. So option A is answer.

Answer 4

b) is incorrect because it accepts string b which is not accepted by the given DFA.

c) is incorrect because it accepts string b which is not accepted by the given DFA

d) is incorrect because it accepts string bba which is not accepted by the given DFA.

 

therefore option a 

Answer 5

A) True.
(B) False, as it accepts string 'b', which is not accepted by original DFA.
(C) False, Same reason as (B).
(D) False, as it accepts string 'bba' which is not accepted by the given DFA.

Answer 6

In question Like these just Apply Partition Algorithm 

It will hardly consume 1.5 minutes.

You will get (A) as an answer