DFA for strings in which leftmost symbol differ from rightmost

We are going to design the DFA for the language, containing strings in which leftmost symbol different from rightmost symbol. Σ is given by {0,1}.

This string should have following rules:

  • The machine will end in the final state q2 if the leftmost symbol is 0 and the rightmost symbol is 1.
  • The machine will end in the final state q4 if the leftmost symbol is 1 and the rightmost symbol is 0.
  • A transition from q0 to q1 is for ‘0’ as the first symbol.
  • A transition from q0 to q4 is for ‘1’ as the first symbol.

Designing DFA step by step:

Step – 1:

Make initial state “q0” then it is the possibility that there would be any ‘b’ but have only ‘a’. So, in this case, we need different string from left and right side.

Step -2:

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

Step -3:

Now create a transition of input alphabet 1 from the state “q1” to state “q2“. And input 0 this put self-loop 0 on state “q1“.

Step -4:

In this step, we need to think of the ending string different from leftmost and rightmost so that we make the opposite string on the other side as shown. The transition of input alphabet 0 from the state “q3” to state “q4“. And input 1 put self-loop 1 on state “q3“.

Step -5:

Final we make the two state “q4” and “q2” as final state. And state of final state should be as shown below.

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 left_rightmost {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the String");
        String str = sc.nextLine();

        Stateq0(str);
    }

    private static void Stateq0(String str) {
        if (str.length() == 0){
            System.out.println("String not Accepted");
        }

        else {
            if(str.charAt(0)=='0')
                Stateq1(str.substring(1));
            else
                Stateq3(str.substring(1));
        }
    }

    private static void Stateq1(String str) {
        if (str.length() == 0){
            System.out.println("String not Accepted");
        }

        else {
            if(str.charAt(0)=='0')
                Stateq1(str.substring(1));
            else
                Stateq2(str.substring(1));
        }
    }

    private static void Stateq2(String str) {
        if (str.length() == 0){
            System.out.println("String Accepted");
        }

        else {
            if(str.charAt(0)=='0')
                Stateq1(str.substring(1));
            else
                Stateq2(str.substring(1));
        }
    }

    private static void Stateq3(String str) {
        if (str.length() == 0){
            System.out.println("String not Accepted");
        }

        else {
            if(str.charAt(0)=='0')
                Stateq4(str.substring(1));
            else
                Stateq3(str.substring(1));
        }
    }

    private static void Stateq4(String str) {
        if (str.length() == 0){
            System.out.println("String Accepted");
        }

        else {
            if(str.charAt(0)=='0')
                Stateq4(str.substring(1));
            else
                Stateq3(str.substring(1));
        }
    }

}

Output:

Enter the String
0101010
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. Number of 1’s is not multiple of 3 on {0,1} using DFA
  5. DFA for Number of 1’s is even/odd and number of 0’s is even/odd
  6. DFA for number of 0’s divisible by five and 1’s divisible by 3
  7. DFA for All string of length at most five
  8. DFA for All strings ending with abb
  9. Design DFA that contain word ‘CAT’ using word ‘CHARIOT’
  10. Design DFA which accept a binary number divisible by 3
  11. Non-Deterministic finite Automata
  12. Design NFA to accept string containing the substring 0101
  13. Design NFA that accepts string ending with aab

Leave a Comment

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

x