Question

The minimum number of nodes in a DFA that recognizes strings over \( \{a, b\} \) with length mod 3 = 0 are _______ .

• A. 4
• B. 2
• C. 3
• D. 1

Hint:

To recognize strings whose length is divisible by 3, a DFA requires at least 3 states to track the remainder of the length modulo 3.

Answer 1

The Correct Option is C

A DFA recognizing strings of length divisible by 3 requires three states, one for each possible remainder when dividing the string's length by 3 (0, 1, and 2). This ensures that the DFA accepts only strings whose length is divisible by 3. Thus, the minimum number of states (nodes) required is 3.