**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:

- 0 -> associated state, q
_{0} - 1 -> associated state, q
_{1} - 2 -> associated state, q
_{2}

– 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

**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:**

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