If the final states and non-final states in the DFA below are interchanged, then which of the following languages over the alphabet {a, b} will be accepted by the new DFA?
(The DFA has: start state q0; on input 'a' from q0 go to q1, on input 'b' from q0 go to q0; on input 'a' from q1 go to q1, on input 'b' from q1 go to q2; on input 'a' from q2 go to q1, on input 'b' from q2 go to q0; final state is q2.)
A. Set of all strings that do not end with ab
B. Set of all strings that begin with either an a or b
C. Set of all strings that do not contain the substring ab
D. Set of all strings described by the regular expression b*(ab)* b*
GATE 2008 · Theory of Computation · Finite Automata · medium
Answer: The new DFA accepts the set of all strings that do not end with ab. Answer: A.
Determine the language of the original DFA: Trace the DFA: q0 is start (non-final). q2 is the only final state. To reach q2, the last transition must be q1 -b-> q2, and to be in q1 just before, the last 'a' must have been read (either from q0 or q1 via self-loop). So q2 is reached exactly when the string ends with 'ab'. Original language L = {w in {a,b}* | w ends with 'ab'}.
Apply DFA complementation: Original final states: {q2}. Original non-final states: {q0, q1}. After swap: final states = {q0, q1}, non-final = {q2}. The new DFA accepts all strings that do NOT end with 'ab'. This matches option A: 'Set of all strings that do not end with ab'.