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

State transition diagram - number of 0's divisible by five and 1's divisible by 3
State transition diagram

Transition table of above DFA:

State transition table - number of 0's divisible by five and 1's divisible by 3
State transition table

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

Code:

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

Recommended:

  1. DFA for Number of 1’s is even/odd and number of 0’s is even/odd
  2. Number of 1’s is a multiple of 3 on {0,1} using DFA
  3. Introduction to Finite Automata
  4. Deterministic Finite Automata (DFA)
  5. Number of 1’s is not multiple of 3 on {0,1} using DFA
  6. Automata Theory and Formal Languages
  7. Kleene Closure
  8. Recursive Definition of a Language
  9. Finite Representation of language

Leave a Comment

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

x