# DFA for number of 0’s divisible by five and 1’s divisible by 3

Design a DFA for a set of string over alphabet {0,1} such that the number of 0’s is divisible by five, and number of 1’s divisible by 3.

#### Solution :

At any instance of time, we will have following cases for number of 0’s.

Case 1 – 5n
Case 2 – 5n + 1
Case 3 – 5n + 2
Case 4 – 5n + 3
Case 5 – 5n + 4

Number of 0’s should be divisible by 5.

Similarly, there will be three cases for number of 1’s.

Case 1 – 3n
Case 2 – 3n + 1
Case 3 – 3n + 2

Thus, depending in number of 0’s and 1’s there will be 5 X 3 = 15 cases.

Let us represent a state of the DFA under consideration as q0 , where I can take a value from 0 to 4 depending on the number of 0’s seen so far:

q0j – number of 0’s is 5n
q1j – number of 0’s is 5n + 1
q2j – number of 0’s is 5n + 2
q3j – number of 0’s is 5n + 3
q4j – number of 0’s is 5n + 4

Similarly, in state q0 can take value from 0 to 2 depending on number of 1’s seen so far.

q0j – number of 1’s is 3n
q1j – number of 1’s is 3n + 1
q2j – number of 1’s is 3n + 2

Transition table of above DFA:

In above table -> represents initial state and * represents final state. In this post, initial and final state is same which is final state.

#### Main.java

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

state00(str);
}

private static void state00(String str) {
if (str.length() == 0){
System.out.println("String Accepted");
}
else {
if(str.charAt(0)=='0')
state10(str.substring(1));
else
state01(str.substring(1));
}
}

private static void state01(String str) {
if (str.length() == 0){
System.out.println("String not accepted");
}
else {
if(str.charAt(0)=='0')
state11(str.substring(1));
else
state02(str.substring(1));
}
}

private static void state02(String str) {
if (str.length() == 0){
System.out.println("String not accepted");
}
else {
if(str.charAt(0)=='0')
state12(str.substring(1));
else
state00(str.substring(1));
}
}

private static void state10(String str) {
if (str.length() == 0){
System.out.println("String not accepted");
}
else {
if(str.charAt(0)=='0')
state20(str.substring(1));
else
state11(str.substring(1));
}
}

private static void state11(String str) {
if (str.length() == 0){
System.out.println("String not accepted");
}
else {
if(str.charAt(0)=='0')
state21(str.substring(1));
else
state12(str.substring(1));
}
}

private static void state12(String str) {
if (str.length() == 0){
System.out.println("String not accepted");
}
else {
if(str.charAt(0)=='0')
state22(str.substring(1));
else
state10(str.substring(1));
}
}

private static void state20(String str) {
if (str.length() == 0){
System.out.println("String not accepted");
}
else {
if(str.charAt(0)=='0')
state30(str.substring(1));
else
state21(str.substring(1));
}
}

private static void state21(String str) {
if (str.length() == 0){
System.out.println("String not accepted");
}
else {
if(str.charAt(0)=='0')
state31(str.substring(1));
else
state22(str.substring(1));
}
}

private static void state22(String str) {
if (str.length() == 0){
System.out.println("String not accepted");
}
else {
if(str.charAt(0)=='0')
state32(str.substring(1));
else
state20(str.substring(1));
}
}

private static void state30(String str) {
if (str.length() == 0){
System.out.println("String not accepted");
}
else {
if(str.charAt(0)=='0')
state40(str.substring(1));
else
state31(str.substring(1));
}
}

private static void state31(String str) {
if (str.length() == 0){
System.out.println("String not accepted");
}
else {
if(str.charAt(0)=='0')
state11(str.substring(1));
else
state32(str.substring(1));
}
}

private static void state32(String str) {
if (str.length() == 0){
System.out.println("String not accepted");
}
else {
if(str.charAt(0)=='0')
state42(str.substring(1));
else
state30(str.substring(1));
}
}

private static void state40(String str) {
if (str.length() == 0){
System.out.println("String not accepted");
}
else {
if(str.charAt(0)=='0')
state00(str.substring(1));
else
state41(str.substring(1));
}
}

private static void state41(String str) {
if (str.length() == 0){
System.out.println("String not accepted");
}
else {
if(str.charAt(0)=='0')
state01(str.substring(1));
else
state42(str.substring(1));
}
}

private static void state42(String str) {
if (str.length() == 0){
System.out.println("String not accepted");
}
else {
if(str.charAt(0)=='0')
state02(str.substring(1));
else
state40(str.substring(1));
}
}
}
```

#### Output:

```Enter the string
01011000
String Accepted```