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	state
Even	Even	q₀
Even	Odd	q₁
Odd	Even	q₂
Odd	Odd	q₃

Designing DFA step by step:

Step -1:

Make initial state “q₀” 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 “q₀” to state “q₁“ and input alphabet ‘0’ from state state “q₀” to state “q₂“.

Step -3:

After number of ‘1’ at “q₁“ are odd 1’s. So, send input alphabet ‘1’ from state “q₁” to state “q₀“ and input alphabet ‘0’ from state “q₁” to state “q₃“.

Step -4:

After step 3 we have got an even number of 1’s at “q₀” and an odd number of 0’s and 1’s “q₁, q₂, q₃”. Now send input alphabet ‘0’ from state “q₂” to state “q₀“ and input alphabet ‘1’ from state “q₂” to state “q₃“.

Step -5:

At this step, we complete the over the machine with “q₃“ 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 “q₀” so make the state “q₀” be the final state.

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 “q₃“ 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 “q₃“ 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

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

Designing DFA step by step:

Step -1:

Step -2:

Step -3:

Step -4:

Step -5:

Code:

Main.java

Output:

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

Designing DFA step by step:

Step -5:

Code:

Main.java

Output:

Recommended:

Leave a Comment Cancel Reply