Can someone explain this conclusion for Finite State Machines?

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
1
down vote

favorite












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 - Both are technically the same thing, check the comments and the answer)



Now 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)






automata finite-automata







share|cite|improve this question



























    up vote
    1
    down vote

    favorite












    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 - Both are technically the same thing, check the comments and the answer)



    Now 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)






    automata finite-automata







    share|cite|improve this question

























      up vote
      1
      down vote

      favorite









      up vote
      1
      down vote

      favorite











      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 - Both are technically the same thing, check the comments and the answer)



      Now 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)






      automata finite-automata







      share|cite|improve this question















      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 - Both are technically the same thing, check the comments and the answer)



      Now 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)






      automata finite-automata




      automata finite-automata






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited 12 mins ago

























      asked 42 mins ago









      Aditya

      14313




      14313




















          1 Answer
          1






          active

          oldest

          votes

















          up vote
          2
          down vote



          accepted










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






          share|cite|improve this answer




















          • Thanks a lot David! I forgot this simple but strong conclusion of LCM's and Divisibility!
            – Aditya
            16 mins ago











          Your Answer




          StackExchange.ifUsing("editor", function ()
          return StackExchange.using("mathjaxEditing", function ()
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
          );
          );
          , "mathjax-editing");

          StackExchange.ready(function()
          var channelOptions =
          tags: "".split(" "),
          id: "419"
          ;
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function()
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled)
          StackExchange.using("snippets", function()
          createEditor();
          );

          else
          createEditor();

          );

          function createEditor()
          StackExchange.prepareEditor(
          heartbeatType: 'answer',
          convertImagesToLinks: false,
          noModals: false,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: null,
          bindNavPrevention: true,
          postfix: "",
          onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          );



          );













           

          draft saved


          draft discarded


















          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f99259%2fcan-someone-explain-this-conclusion-for-finite-state-machines%23new-answer', 'question_page');

          );

          Post as a guest

















          1 Answer
          1






          active

          oldest

          votes








          1 Answer
          1






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes








          up vote
          2
          down vote



          accepted










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






          share|cite|improve this answer




















          • Thanks a lot David! I forgot this simple but strong conclusion of LCM's and Divisibility!
            – Aditya
            16 mins ago















          up vote
          2
          down vote



          accepted










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






          share|cite|improve this answer




















          • Thanks a lot David! I forgot this simple but strong conclusion of LCM's and Divisibility!
            – Aditya
            16 mins ago













          up vote
          2
          down vote



          accepted







          up vote
          2
          down vote



          accepted






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






          share|cite|improve this answer












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







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered 20 mins ago









          David Richerby

          63.3k1596181




          63.3k1596181











          • Thanks a lot David! I forgot this simple but strong conclusion of LCM's and Divisibility!
            – Aditya
            16 mins ago

















          • Thanks a lot David! I forgot this simple but strong conclusion of LCM's and Divisibility!
            – Aditya
            16 mins ago
















          Thanks a lot David! I forgot this simple but strong conclusion of LCM's and Divisibility!
          – Aditya
          16 mins ago





          Thanks a lot David! I forgot this simple but strong conclusion of LCM's and Divisibility!
          – Aditya
          16 mins ago


















           

          draft saved


          draft discarded















































           


          draft saved


          draft discarded














          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f99259%2fcan-someone-explain-this-conclusion-for-finite-state-machines%23new-answer', 'question_page');

          );

          Post as a guest
































































          Comments

          Post a Comment

          Popular posts from this blog

          What does second last employer means? [closed]

          Image
          Clash Royale CLAN TAG #URR8PPP .everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0; up vote -3 down vote favorite Say, for example I have worked in the following companies, Company A => 2010 - 2011 Company B => 2011 - 2012 Company C => 2012 - Till Date Company D => Have offer Now assume Company D is asking to submit documents from my second last employer. So from the list of companies given, which company would be qualified as second last employer? software-industry employer share | improve this question asked Aug 10 '14 at 5:16 Rajaprabhu Aravindasamy 559 1 6 13 closed as off-topic by Jim G., jmort253 ♦ Aug 11 '14 at 1:58 This question appears to be off-topic. The users who voted to close gave this specific reason: "Questions seeking advice on company-specific regulations, agreements, or policies should be directed to your manager or HR department. Questions that address...
          Read more

          List of Gilmore Girls characters

          Image
          The season three cast—(Back row): Lane, Michel, Paris, Emily, Richard, Sookie, Miss Patty, Kirk; Front row: Jess, Luke, Lorelai, Rory, Dean This is a list of characters for the comedy-drama television series Gilmore Girls . Contents 1 Main characters 1.1 Lorelai Gilmore 1.2 Rory Gilmore 1.3 Sookie St. James 1.4 Lane Kim 1.5 Michel Gerard 1.6 Luke Danes 1.7 Emily Gilmore 1.8 Richard Gilmore 1.9 Paris Geller 1.10 Dean Forester 1.11 Jess Mariano 1.12 Kirk Gleason 1.13 Jason Stiles 1.14 Logan Huntzberger 2 Major recurring characters 2.1 Christopher Hayden 2.2 Jackson Belleville 2.3 Mrs. Kim 2.4 Tristin DuGray 2.5 Max Medina 2.6 Taylor Doose 2.7 Dave Rygalski 2.8 Marty 3 Recurring characters 3.1 Stars Hollow 3.2 Chilton 3.3 Yale 3.4 Other 4 Notable guest stars 5 Unseen characters 6 Notes 7 References Main characters Actor Character Appearances Season 1 Season 2 Season 3 Season 4 Season 5 Season 6 Season 7 A Year in the Life Lauren Graham Lorelai Gilmore...
          Read more

          Confectionery

          Image
          Prepared foods made with a lot of sugar or other cabohydrates "Sweetmeat" redirects here. For the racehorse, see Sweetmeat (horse). Not to be confused with Sweetbread. This Kransekake is a traditional Scandinavian baker's confection. Confectionery is the art of making confections , which are food items that are rich in sugar and carbohydrates. Exact definitions are difficult. [1] In general, though, confectionery is divided into two broad and somewhat overlapping categories, bakers' confections and sugar confections. [2] Bakers' confectionery, also called flour confections , includes principally sweet pastries, cakes, and similar baked goods. Sugar confectionery includes candies ( sweets in British English), candied nuts, chocolates, chewing gum, bubble gum, pastillage, and other confections that are made primarily of sugar. In some cases, chocolate confections (confections made of chocolate) are treated as a separate category, as are sugar-free versions of ...
          Read more