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

Number of 1’s is not multiple of three. Let L be a language over alphabets {0, 1} such that number of 1’s is multiple of 3.

Thus, L = [ ω  ϵ  {0, 1}* | no. of 1’s in ω is multiple of 3]

Complement of L is given by :

L’ = [ ω  ϵ  {0, 1}* | no. of 1’s in ω is not multiple of 3]

DFA for L’ can be obtained through following modification on DFA for L.

  1. 1. Every final state of L should become a non – accepting state is L’.
  2. 2. Every non-accepting state of L should become a final state in L’.

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 not multiple of 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“.

Number of 1’s is not multiple of 3

Step -2:

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

Number of 1’s is not 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“.

Number of 1’s is not multiple of 3

Step -4:

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

Number of 1’s is not 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“.

Number of 1’s is not multiple of 3

Step -6:

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

Number of 1’s is not multiple of 3

Transition table of above DFA:

Transition table of Number of 1’s is not multiple of 3

Code:

Main.java

package com.company.finite_automata;

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

        checkStateA(str);
    }

    private static void checkStateA(String str) {
        if (str.length() == 0){
            System.out.println("string not 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 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 Accepted");
        }
        else {
            if(str.charAt(0)=='0')
                stateC(str.substring(1));
            else
                checkStateA(str.substring(1));
        }
    }
}

Output:

Enter the String
10101
string not accepted

Recommended:

  1. Introduction to Finite Automata
  2. Deterministic Finite Automata (DFA)
  3. Number of 1’s is a 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
  8. Introduction to Finite Automata
  9. Deterministic Finite Automata (DFA)

Leave a Comment

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

x