Automata, Snippets

Finite State Machine: Check Whether a Number is Divisible by 3

Leave a comment

A Finite State Machine (FSM) can determine whether a decimal integer is divisible by 3 without performing any division. The key insight is that a number is divisible by 3 if and only if the sum of its digits is divisible by 3. We can track the running digit-sum modulo 3 as we process each digit, mapping perfectly onto a 3-state FSM: State 0 (remainder 0), State 1 (remainder 1), and State 2 (remainder 2). After processing all digits, the machine is in State 0 if and only if the number is divisible by 3. The FSM also prints a state trace as it processes each digit.

FSM for Divisibility by 3 in Java

import java.io.*;

class FsmDivisibleByThree {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        System.out.println("Enter a number:");
        String numberString = reader.readLine();

        int currentState = 0;  // FSM state = (digit-sum mod 3); start at remainder 0

        System.out.print("q0");  // Print initial state

        for (int i = 0; i < numberString.length(); i++) {
            char digit = numberString.charAt(i);

            /**
             * Each digit belongs to one of three residue classes mod 3:
             *   Residue 0: digits 0, 3, 6, 9  -- digit % 3 == 0, no change to remainder
             *   Residue 1: digits 1, 4, 7     -- digit % 3 == 1, adds 1 to remainder
             *   Residue 2: digits 2, 5, 8     -- digit % 3 == 2, adds 2 to remainder
             *
             * New state = (currentState + digitResidue) % 3
             */
            switch (digit) {
                // Digits with residue 0: new state = currentState (unchanged)
                case '0': case '3': case '6': case '9':
                    switch (currentState) {
                        case 0: currentState = 0; break;  // 0+0=0 mod 3
                        case 1: currentState = 1; break;  // 1+0=1 mod 3
                        case 2: currentState = 2; break;  // 2+0=2 mod 3
                    }
                    break;

                // Digits with residue 1: new state = (currentState + 1) % 3
                case '1': case '4': case '7':
                    switch (currentState) {
                        case 0: currentState = 1; break;  // 0+1=1 mod 3
                        case 1: currentState = 2; break;  // 1+1=2 mod 3
                        case 2: currentState = 0; break;  // 2+1=3=0 mod 3
                    }
                    break;

                // Digits with residue 2: new state = (currentState + 2) % 3
                case '2': case '5': case '8':
                    switch (currentState) {
                        case 0: currentState = 2; break;  // 0+2=2 mod 3
                        case 1: currentState = 0; break;  // 1+2=3=0 mod 3
                        case 2: currentState = 1; break;  // 2+2=4=1 mod 3
                    }
                    break;
            }

            System.out.print(" ->q" + currentState);  // Print state after each digit
        }

        System.out.println();
        System.out.println("Is " + numberString + " divisible by 3?");
        if (currentState == 0) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

How the Code Works

  1. Three states represent the running remainder: State 0 = remainder 0, State 1 = remainder 1, State 2 = remainder 2. The FSM starts in State 0 (an empty number has remainder 0).
  2. Digit grouping by residue class: Digits are grouped as residue-0 (0,3,6,9), residue-1 (1,4,7), and residue-2 (2,5,8). Adding a digit from residue class r transitions to (currentState + r) % 3.
  3. Inner switch on currentState explicitly computes the new state for each digit residue group, directly encoding the FSM’s transition function.
  4. State trace prints each transition after every digit, visualising the machine’s path through states as it reads the number.
  5. Decision: After all digits are consumed, currentState == 0 means the full digit-sum is divisible by 3, so the number itself is divisible by 3.

Sample Output

Enter a number:
462
q0 ->q1 ->q1 ->q0
Is 462 divisible by 3?
Yes

Enter a number:
535
q0 ->q2 ->q2 ->q1
Is 535 divisible by 3?
No

Output Explanation

  1. For 462: digit 4 (residue 1) takes q0→q1; digit 6 (residue 0) takes q1→q1; digit 2 (residue 2) takes q1→q0 (since 1+2=3≡0 mod 3). Final state is q0 → Yes, divisible by 3. Indeed 4+6+2=12, divisible by 3.
  2. For 535: digit 5 (residue 2) takes q0→q2; digit 3 (residue 0) takes q2→q2; digit 5 (residue 2) takes q2→q1 (since 2+2=4≡1 mod 3). Final state is q1 → No, not divisible by 3. Indeed 5+3+5=13, not divisible by 3.

See Also

Conclusion

This FSM elegantly shows how divisibility rules translate directly into state machines. The three-state machine perfectly captures the modular arithmetic of divisibility by 3, processing the number one digit at a time in a single pass. This pattern generalises: you can build an FSM for divisibility by any integer n using exactly n states, where each state represents one of the n possible remainders.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.