Number of 1’s is a multiple of 3 on {0,1} using DFA

Finite automata or finite state machine can be thought of as a severely restricted model of a computer.

Finite state machine that are acceptable only input alphabet‘0’ and ‘1’.

  • Determine the initial state.
  • The transition occurs on every input alphabet.
  • Determine whether the self-loop should apply or not.
  • Mark’s final state.

Designing DFA step by step:

Step -1:

Make initial state “q0” then it is the possibility that there would not be any ‘1’ but have only ‘0’ in the string which is acceptable because 1 is multiple by 3. So, in this case, any number of 0’s can be present here and for this self-loop of ‘0’ on initial state “q0“.

initial state of Number of 1's is a multiple of 3

Step -2:

Create transition of input alphabet ‘1’ from state “q0” to state “q1“.

step 2 Number of 1's is a multiple of 3

Step -3:

After one ‘1’ any number of 0’s can be present i.e, no ‘0’ or more than one ‘1’. For this put self-loop ‘0’ on state “q1“.

step 3 Number of 1's is a multiple of 3

Step -4:

Now create transition of input alphabet ‘1’ from state “q1” to state “q2“.

step 4 Number of 1's is a multiple of 3

Step -5:

After that two 1’s any number of 0’s can be found in the string and for this put self loop of 1’s on initial state “q2“.

step 5 Number of 1's is a multiple of 3

Step -6:

Before transition of third ‘1’ we need to think about the logic so that after the transition the machine will accept string the number of ones multiple by 3. For this transit ‘1’ from state “q2” to state “q0“. As third one is reach to state “q0” so make state “q0” be final state.

step 6 Number of 1's is a multiple of 3

Transition table of above DFA:

transition table of Number of 1's is a multiple of 3

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);
        String str = sc.nextLine();

        checkStateA(str);
    }

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

        else {
            if(str.charAt(0)=='0')
                checkStateA(str.substring(1));
            else
                stateB(str.substring(1));
        }
    }

    private static void stateB(String str) {

        if(str.length() == 0){
            System.out.println("string not accepted");
        }
        else {
            if(str.charAt(0)=='0')
                stateB(str.substring(1));
            else
                stateC(str.substring(1));
        }
    }

    private static void stateC(String str) {

        if(str.length() == 0){
            System.out.println("string not accepted");
        }
        else {
            if(str.charAt(0)=='0')
                stateC(str.substring(1));
            else
                checkStateA(str.substring(1));
        }
    }
}

Output:

Enter the String
10101
String Accepted

Recommended:

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

1 thought on “Number of 1’s is a multiple of 3 on {0,1} using DFA”

  1. Howdy just wanted to give you a quick heads up.

    The text in your article seem to be running off the screen in Safari.
    I’m not sure if this is a formatting issue or something to do with internet browser
    compatibility but I figured I’d post to let you know.
    The design look great though! Hope you get the
    problem fixed soon. Kudos

Leave a Comment

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

x