Deterministic automaton whose input length is divisible by 3 or 5?

Question

I only have one letter available as a language (e.g.: x). If I now enter "xxx" or "xxxxx" then the machine should accept this input because in the former case the length is 3 and in the second the length of the input is 5. And since the length should be divisible by 3 or 5, this should be accepted.

However, after hours of thinking, I can't find the solution. Can someone help me please?

I have tried the following: q0, q1, q2, q3, q4 and q5 --> each for the rest.

q3 and q5 would be my final states, since the remainder is 0 (divisible)

Then I can enter the following transitions:

 q0 --> q1
 q1 --> q2
 q2 --> q3
 q3 --> q4
 q4 --> q5
 q5 --> q6

For example, if I have 6 "x" i.e. "xxxxxx" then I end up in state q0. So it has to be an accepting one too.

If I have 10 "x", i.e. "xxxxxxxxxx" I end up on q4. With 11 "x" I end up at q5, which is an accepting state which is not possible.

No matter how I spin it, I keep running into problems like this. Why am I thinking so wrongly here :-S

Answer 1

If you need to validate both multiples of n and m, start by just writing out every possible state until things repeat, which would be n x m states. So for n=3 and m=5:

S
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Then you mark terminals:

 S
 1
 2
(3)
 4
(5)
(6)
 7
 8
(9)
(10)
 11
(12)
 13
 14
(15)

And then you optimize by removing irrelevant nodes. For example, we don't need to visit 7, and then 8, just to get to 9, we can remove 8 and instead make the path from the non-terminal 7 to the terminal (9) consume two tokens. If we don't have that many tokens to consume, the DFA halts in a non-terminal state.