# Can someone explain this conclusion for Finite State Machines?

PS It isn't a homework problem.. (But the results seems to be working for me when I checked manually a couple of values of m and n)

Let's say I have two FSM's(calling them A and B)

• A is the the machine for checking divisibility by any +ve number (calling it m)
• B is the the machine for checking divisibility by any +ve number (calling it n) (m and n aren't equal)

Now we have a third machine (C) for which we need to find the number of states it will have if the goal of that machine is A machine(FSM) which will accept Divisibility of both $$n$$ and $$m$$)

So here are the claims for the count of states for $$C$$,

• if $$GCD (m,n)$$ equivalent to $$1$$, then the number of states in C is $$m*n$$

• if $$GCD (m,n)$$ isn't equivalent to $$1$$, then number of states in C is $$LCM(m,n)$$

(EDIT 1- Both are technically the same thing, check the comments and the answer)

(Edit -2 I meant this, if we have strings given to us over {0,1}, and the machines will then calculate the divisibility by the given number and with result in either of the (let's say the number we are dividing with is n) n-1 states as we can have n-1 modulo values possible)

I have checked the results for few m and m manually and they seem to be correct for them..

But why it's so?(I know that A and B will have m and n as count of states respectively for minimal DFA)

• Just to check -- when you say "divisibility by $n$", you're asking about the length of the input being divisible by $n$, right? (Which is equivalent to the input being treated as a number written in unary.) – David Richerby Oct 29 '18 at 17:14
• @David Richerby I meant this, if we have strings given to us over {0,1}, and the machines will then calculate the divisibility by the given number and with result in either of the (let's say the number we are dividing with is n) n-1 states as we can have n-1 modulo values possible.. PS I am confused what the comments meant as unary (only a single value/symbol?) – Aditya Oct 30 '18 at 2:47
• In that case, I'll need to edit my answer. I was assuming unary. – David Richerby Oct 30 '18 at 11:21
• Thanks David but to keep this one too; might help any future visitor too, Thanks:) – Aditya Oct 30 '18 at 11:39

In both cases, the number of states is the LCM. This is because a number is divisible by $$m$$ and $$n$$ if, and only if, it is divisible by $$\mathrm{lcm}(m,n)$$ and, for any positive integer $$d$$, you can check that the input length is divisible by $$d$$ by having states $$\{0, \dots, d-1\}$$ such that the automaton is in state $$i$$ when the number of characters read is congruent to $$i$$, modulo $$d$$.
• @kasperd In the context of automata theory, it's a standard exercise to recognize the language of multiples of some number, written in unary. It's also very common to consider single-character alphabets and the alphabet $\{0,1\}$, but very unusual to consider alphabet $\{0,\dots,9\}$. This all suggests the question is unlikely to be about decimal. I agree that an explicit clarification would be useful. My answer implicitly states that the number is in unary: I refer to "the input length [being] divisible by $d$" and to "the number of characters read". – David Richerby Oct 29 '18 at 17:13