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



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.
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:
- Number of 1’s is a multiple of 3 on {0,1} using DFA
- Introduction to Finite Automata
- Deterministic Finite Automata (DFA)
- Number of 1’s is not multiple of 3 on {0,1} using DFA
- Automata Theory and Formal Languages
- Kleene Closure
- Recursive Definition of a Language
- Finite Representation of language