FSA to find whether a binary number is divisible by 3

The procedure can be explained as follows: Scan the list of numbers and keep looking for the remainder of the string when divided by 3.

There are three cases (and states):

  1. When the remainder is zero: When we are in this state, no matter how many zeros we add, we will get a remainder of zero. If we add a 1, then the remainder is 1 and it goes to state 1
  2. When the remainder is one: If we add 1, then it is equivalent to multiplying the number by 2 and adding one – which means if we had x that had remainder 1, then now we have (2x+1)%3, which is equivalent to 3%3, which is zero. Hence it goes to state 1. When we add 0, then we multiply the number by 2, whence the remainder becomes 2 and it goes to state 2.
  3. When the remainder is two: If we add 0 to it, then we are multiplying the number by 2. When x%3 is 2, by simple arithmetic we can find that (2x)%3 is 1, so it goes to state 1.  If we add 1 to it, then (2x+1)%3 is 2 only (again by simple arithmetic) in which case it remains in state 2.

Using this reasoning, we can construct a DFA to check for divisibility by any number.

Advertisements

One thought on “FSA to find whether a binary number is divisible by 3

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s