How can I calculate the minimum DFA's number of states accepting strings whose length is not multiple of 9 based on an alphabet composed by 4 symbols?
My attempt is:
$L = \{w \in \{a,b,c,d\}^* : \text{9 does not divide |w|}\}$
that means there is not a whole number $z$ such that $|w| = 9\cdot z$
therefore $|w| \in \mathbb{N} - \{9, 18, 27, ...\}$
The number of characters in the alphabet is irrelevant, since you’re interested only in the length of the word. In order to recognize when the length is a multiple of $9$, you need $9$ states, one for each possible remainder. The best that you can do is ring of $9$ states, all of them acceptor states except the initial state. If you’re not sure, start with that DFA and apply the algorithm to minimize it.
