Design DFA which accept a binary number divisible by 3

Design of DFA divisibility – by – 3 tester for a binary number.

A binary number is divisible by 3, if the remainder when divided by 3 will work out to be zero. We must device a mechanism for finding the final remainder.

– We can calculate the running remainder based on previous remainder and the next input.

– The running remainder could be:

  1. 0 -> associated state, q0
  2. 1 -> associated state, q1
  3. 2 -> associated state, q2

– Starting with the most significant bit, input is taken one bit at a time. Running remainder is calculated after every input.

The process of finding the running remainder is being explaining with the help of an example.

Number to be divided : 101101

Design DFA which accept a binary number divisible  by 3
State Transition Diagram
State Transition Table

Code:

Main.java

import java.util.Scanner;

public class divisible_by_3 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the String");
        String str = sc.nextLine();

        Stateq0(str);
    }

    private static void Stateq0(String str) {
        if (str.length() == 0){
            System.out.println("String Accepted");
        }

        else {
            if(str.charAt(0)=='0')
                Stateq0(str.substring(1));
            else
                Stateq1(str.substring(1));
        }
    }


    private static void Stateq1(String str) {
        if (str.length() == 0){
            System.out.println("String not Accepted");
        }

        else {
            if(str.charAt(0)=='0')
                Stateq2(str.substring(1));
            else
                Stateq0(str.substring(1));
        }
    }

    private static void Stateq2(String str) {
        if (str.length() == 0){
            System.out.println("String not Accepted");
        }

        else {
            if(str.charAt(0)=='0')
                Stateq1(str.substring(1));
            else
                Stateq2(str.substring(1));
        }
    }

}

Output:

Enter the String
101101
String Accepted

Recommended:

  1. Introduction to Finite Automata
  2. Deterministic Finite Automata (DFA)
  3. Number of 1’s is a multiple of 3 on {0,1} using DFA
  4. Number of 1’s is not multiple of 3 on {0,1} using DFA
  5. DFA for Number of 1’s is even/odd and number of 0’s is even/odd
  6. DFA for number of 0’s divisible by five and 1’s divisible by 3
  7. DFA for All string of length at most five
  8. DFA for All strings ending with abb
  9. DFA for strings in which leftmost symbol differ from rightmost
  10. Design DFA that contain word ‘CAT’ using word ‘CHARIOT’
  11. Design DFA which accept a binary number divisible by 3
  12. Non-Deterministic finite Automata
  13. Design NFA to accept string containing the substring 0101
  14. Design NFA that accepts string ending with aab

Leave a Comment

Your email address will not be published. Required fields are marked *

x