DFA for All strings ending with abb

This can be seen as extension of solution which given below diagrams as the sub string ‘abb’ should be at the end of the string. Transitions from q3 should be modified to handle the string has to end in ‘abb’.

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, any number of b’s can be present here and for this self-loop of ‘b’ on initial state “q0”.

Step -2:

Create transition of input alphabet ‘a’ from state “q0” to state “q1“ and input ‘b’ this put self-loop ‘b’ on state “q1“.

Step -3:

Now create a transition of input alphabet ‘b’ from the state “q1” to state “q2“. And input alphabet ‘a’ from the state “q2” to state “q1“ because if a go back to q1 then ending of the string will remain ‘abb’.

Step -4:

In this step, we need to think of the ending string by ‘abb’ so that after the transition the machine will accept the string of ending ‘abb’. For this transit ‘b’ from the state “q2” to state “q3“ and transition of “q3“ of ‘a’ and ‘b’ go-to “q1” to state “q0“. As string generates at “q3“ is ‘abb’ so make the state “q3“ be the final state.

Transition diagram - All strings ending with abb
Transition Diagram

Transition table of above DFA:

Transition table - All strings ending with abb
Transition Table

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 ending_in_abb {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the string");
        String str = sc.nextLine();

        stateA(str);
    }

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

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

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

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

}

Ourput:

Enter the string
ababababaabb
String Accepted

Recommended:

  1. DFA for All string of length at most five
  2. DFA for number of 0’s divisible by five and 1’s divisible by 3
  3. DFA for Number of 1’s is even/odd and number of 0’s is even/odd
  4. Number of 1’s is a multiple of 3 on {0,1} using DFA
  5. Introduction to Finite Automata
  6. Deterministic Finite Automata (DFA)
  7. Number of 1’s is not multiple of 3 on {0,1} using DFA
  8. Automata Theory and Formal Languages
  9. Kleene Closure
  10. Recursive Definition of a Language
  11. Finite Representation of language

Leave a Comment

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

x