How is possible to construct a finite state transducer that multiplies a number by 5? We can assume that numbers are supplied in binary notation, from least significant bits to most significant.

  • $\begingroup$ Do you know how to multiply by 2? By 3? $\endgroup$ – Yuval Filmus Dec 17 '20 at 14:07
  • $\begingroup$ How are the numbers encoded? $\endgroup$ – Yuval Filmus Dec 17 '20 at 14:08
  • 1
    $\begingroup$ If you don't know how to multiply by 2, you won't be able to multiply by 5. I suggest starting with multiplying by 2, then moving on to multiplying by 3, then by 4, and only then by 5. $\endgroup$ – Yuval Filmus Dec 17 '20 at 14:20
  • 2
    $\begingroup$ No. That's something you should be able to work out on your own. $\endgroup$ – Yuval Filmus Dec 17 '20 at 14:25
  • 2
    $\begingroup$ If you can multiply by 3 by simulating x+2x, then you can multiply by 5 by simulating x+4x. $\endgroup$ – Yuval Filmus Dec 17 '20 at 19:30

Your Answer

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

Browse other questions tagged or ask your own question.