Let \(L\) be the language represented by the regular expression…
2015
Let \(L\) be the language represented by the regular expression \(Σ^∗0011Σ^∗\)where \(Σ = \{0, 1\}\). What is the minimum number of states in a DFA that recognizes \(\overline L\) (complement of \(L\))?
- A.
4
- B.
5
- C.
6
- D.
8
Attempted by 144 students.
Show answer & explanation
Correct answer: B
Key idea: track the length of the longest suffix that matches a prefix of 0011.
States: use five states 0,1,2,3,4. State k (0 ≤ k ≤ 3) means the last k symbols equal the first k symbols of 0011. State 4 means the substring 0011 has occurred.
Construction: for the language of strings that contain 0011, make state 4 an accepting sink and the other states nonaccepting. For the complement (strings that do NOT contain 0011), accept states 0–3 and make state 4 a rejecting sink. This uses 5 states.
Minimality: the strings that end with different lengths k (k = 0,1,2,3) of a prefix of 0011 are pairwise distinguishable — appending the remaining suffix of 0011 will lead to occurrence only from the correct k. The class of strings that have already seen 0011 is also distinct. Hence there are at least 5 Myhill–Nerode equivalence classes.
Conclusion: the minimal number of states in a DFA for the complement of Σ*0011Σ* is 5.
A video solution is available for this question — log in and enroll to watch it.