Determine the language recognized by the following DFA?
Determine the language recognized by the following DFA?
Answer: C. Strings containing at least two 0's and at least two 1's — Answer: Strings containing at least two 0's and at least two 1's. Key idea: The DFA has nine states that track, independently for 0 and 1, whether the count…
- A.
Strings containing even 0's and even 1's
- B.
Strings containing exactly two 0's and exactly two 1's
- C.
Strings containing at least two 0's and at least two 1's
- D.
None of these
Attempted by 247 students.
Show answer & explanation
Correct answer: C
Answer: Strings containing at least two 0's and at least two 1's.
Key idea: The DFA has nine states that track, independently for 0 and 1, whether the count seen so far is 0, 1, or at least 2. The accepting state represents both counts being at least two.
Start state corresponds to seeing 0 zeros and 0 ones.
Transitions on 0 or 1 move you to states that increase the corresponding count, with each count saturating at the "at least 2" level.
The sole accepting state is reached only after both counts are in the "at least 2" category; that state loops on both 0 and 1 so any additional symbols are allowed.
Therefore the language is all binary strings that contain at least two 0's and at least two 1's.