1

I want to create a finite state machine that takes strings with only 0 and 1 as input. The finite state machine shall only accept strings with an odd number of zeros and the sum of the numbers in the string should be divisible by 3 (but any other numbers). So 0111 should be accepted, but not 011 or 111.

enter image description here

I made the picture above (sorry for the ugly drawing, its difficult to draw with a mouse ;) ) as a finite state machine which only gives back a 1 if the strings sum is divisible by 3 but how do I make it only accept strings with an odd number of zeros as well?

If the drawing includes errors, please also tell me that. (Im new to this)

Tommy
  • 19
  • 2
    Please comment why you downvote – Tommy Oct 25 '22 at 22:01
  • 5
    You wrote down a state machine that accepts strings of 1s and 0s that add up to 3. Can you find the state machine the accepts strings with an odd number of zeros? If you can write down both of these state machines, there is a standard operation for "combining" them into a single machine that will accept only if both conditions are met. It uses the Cartesian product of the states – Nathan Lowry Oct 25 '22 at 22:02
  • Can you link to some information about the combining operation? Because I can't find anything about how to do it. – Tommy Oct 25 '22 at 22:08
  • 1
    This should cover everything you need: courses.engr.illinois.edu/cs373/sp2010/lectures/lect_04.pdf. In your case, you'll basically make two copies of the state machine you already drew and you'll jump back and forth between them whenever you read a zero. – Nathan Lowry Oct 25 '22 at 22:12

0 Answers0