Consider the DFAs M and N given above. The number of states in a minimal DFA…
2015
Consider the DFAs M and N given above. The number of states in a minimal DFA that accepts the language L(M) ∩ L(N) is____________________
Attempted by 156 students.
Show answer & explanation
Correct answer: 1
Key insight: determine the language each DFA accepts and then their intersection.
The first DFA (M) has two states: the accepting state is reached exactly when the last symbol read is a. So L(M) = all strings over {a,b} that end with a.
The second DFA (N) is symmetric but accepts exactly the strings that end with b: L(N) = all strings over {a,b} that end with b.
Their intersection consists of strings that end with both a and b simultaneously, which is impossible. Thus the intersection is the empty language.
The minimal DFA for the empty language has a single non-accepting state with self-loops on all alphabet symbols, so it has 1 state.
A video solution is available for this question — log in and enroll to watch it.