# 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

#### 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```