Answer

Correct Option: (ii) 3

Explanation

To check divisibility by $3$, we only need the remainder modulo 3 of the number. Whether the input is binary, decimal, or octal does not change the number of remainders.

For modulus $3$, there are exactly $3$ possible remainders:

• $r = 0$ → number divisible by 3 (accepting state)
• $r = 1$ → remainder 1
• $r = 2$ → remainder 2

DFA Construction for Octal Alphabet

• Alphabet: $\Sigma = \{0,1,2,3,4,5,6,7\}$
• States: $q_0, q_1, q_2$ representing remainder $0,1,2$
• Start state: $q_0$ (value 0)
• Accepting state: $q_0$
• Transition: On reading octal digit $d$ from state $q_r$,
  $$\delta(q_r, d) = q_{(r \times 8 + d) \bmod 3}$$
  Since $8 \equiv 2 \pmod 3$, this simplifies to $q_{(2r + d) \bmod 3}$.

This DFA is complete and minimal – each remainder is distinguishable (Myhill-Nerode equivalence).

Why other options are wrong

• (i) 1 state: would accept all or no strings, cannot distinguish remainders.
• (iii) 5 and (iv) 7: unnecessary extra states; $\lceil \log_2 3 \rceil$ is not relevant.

Final Answer

Minimum number of states = 3 (one per residue class mod 3).