GATE 2015 CS – Question 49
[Two DFAs, each with two states. DFA M: the start state loops on b, reads a to move to the final state, the final state loops on a and reads b to return to the start state. DFA N: the start state loops on a, reads b to move to the final state, the final state loops on b and reads a to return to the start state.]
Consider the DFAs M and N given above. The number of states in a minimal DFA that accepts the language $L(M) \cap L(N)$ is ________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 1
Explanation
In M the final state is reached by reading a, and it is left only on b, so M accepts the strings that end in a. In N the final state is reached by reading b, so N accepts the strings that end in b. No string ends in both, so $L(M) \cap L(N)$ is empty. The minimal DFA for the empty language has a single non-accepting state.