My question is inspired by The number of states in DFA that accepts strings with length that is divisible by $3$ or $5$. 's conclusion, that DFA requires full a*b number of states. So - I am trying to construct PFA (probabilistic finita automata) which accepts words of legnth divisble by m=ab (where a and b are distinct primes) with probability 1 (but can reject all other words - whose length can not be divided by m). Can such PFA have less that m=ab states?
I am tempted to devise algorithm with approx a+b states, that uses some kind of factorization, but the idea about factorizaion requires that we track 2 states - one from each subset of a and b, that is contradictory to the idea about FA (without any memory).