GATE 2011 CS (CS1) – Question 55
DFA D has transitions p:a→s,b→q; q:a→t,b→r; r loops on a,b; s,t are accepting and each loops on a,b. Which displayed DFA is an equivalent minimal machine?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) DFA A
Explanation
Accepting sink states s,t have identical right languages and merge. The remaining p,q,r cannot merge: p and q differ on suffix ba, and r rejects a while each of p,q accepts it. Thus the minimum has four states with p→accept on a, p→q on b, q→accept on a, q→r on b. Diagram A shows this, so A.