DFA for Number of 1’s is even/odd and number of 0’s is even/odd

Number of 1’s is even and the number of 0’s is even

At any instance of time, we will have following cause for number of 0’s and number of 1’s seen by the machine.

Situations
state
Number of 0’s Number of 1’s
Even Even q0
Even Odd q1
Odd Even q2
Odd Odd q3

Designing DFA step by step:

Step -1:

Make initial state “q0” then it is that possibility that there would not be any “1” or “0” as, empty string contain even number of 0’s and even number of 1’s.

DFA for Number of 1's is even/odd and number

Step -2:

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

DFA for Number of 1's is even/odd and number

Step -3:

After number of ‘1’ at “q1“ are odd 1’s. So, send input alphabet ‘1’ from state “q1” to state “q0“ and input alphabet ‘0’ from state “q1” to state “q3“.

DFA for Number of 1's is even/odd and number

Step -4:

After step 3 we have got an even number of 1’s at “q0” and an odd number of 0’s and 1’s “q1, q2, q3”. Now send input alphabet ‘0’ from state “q2” to state “q0“ and input alphabet ‘1’ from state “q2” to state “q3“.

DFA for Number of 1's is even/odd and number

Step -5:

At this step, we complete the over the machine with “q3“ so that after the transition the machine will accept the string the number of ‘1’ and ‘0’ are even. As last even number of ‘1’ and ‘0’ reach to “q0” so make the state “q0” be the final state.

DFA for Number of 1's is even/odd and number

Transition table of above DFA:

Transition table of DFA for Number of 1's is even/odd and number

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();

        checkStateA(str);
    }

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

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

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

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

Output:

Enter the string
101010
String not accepted

Number of 1’s is Odd and the number of 0’s is Odd

In solution of give question, the state “q3“ stands for odd number of 0’s should be declared as final state.

Designing DFA step by step:

Step -5:

Number of 1’s and 0’s even question above all step are same just make change in final state to “q3“ to get odd number of 0’s and 1’s.

Number of 1's is Odd and the number of 0's is Odd

Transition table of above DFA:

Transition table of Number of 1's is Odd and the number of 0's is Odd

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();

        checkStateA(str);
    }

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

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

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

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

Output:

Enter the string
101010
String Accepted

Recommended:

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

Leave a Comment

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

x