2
$\begingroup$

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)

$\endgroup$
  • 2
    $\begingroup$ 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.) $\endgroup$ – David Richerby Oct 29 '18 at 17:14
  • $\begingroup$ @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?) $\endgroup$ – Aditya Oct 30 '18 at 2:47
  • $\begingroup$ In that case, I'll need to edit my answer. I was assuming unary. $\endgroup$ – David Richerby Oct 30 '18 at 11:21
  • $\begingroup$ Thanks David but to keep this one too; might help any future visitor too, Thanks:) $\endgroup$ – Aditya Oct 30 '18 at 11:39
4
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Thanks a lot David! I forgot this simple but strong conclusion of LCM's and Divisibility! $\endgroup$ – Aditya Oct 29 '18 at 13:31
  • $\begingroup$ Some numbers can be checked with fewer states. For example you only need 2 states to verify divisibility by 10. $\endgroup$ – kasperd Oct 29 '18 at 15:56
  • $\begingroup$ @kasperd I'm assuming that the "number" is actually the length of the input (i.e., the number is in unary). Nothing in the question says anything about decimal and the trick you suggest only works with bases that are a multiple of five. $\endgroup$ – David Richerby Oct 29 '18 at 16:07
  • $\begingroup$ @Aditya In decimal, you just need to check if the last digit you saw was a zero or five, so you just need two states: "last digit was 0 or 5" and "last digit was not 0 or 5". $\endgroup$ – David Richerby Oct 29 '18 at 16:23
  • 1
    $\begingroup$ @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". $\endgroup$ – David Richerby Oct 29 '18 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.