# 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.

### 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“.

### 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“.

### 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“.

### 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.

Transition table of above DFA:

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

#### 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.

Transition table of above DFA:

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

#### 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```