Design DFA that contain word ‘CAT’ using word ‘CHARIOT’

We are going to design a DFA that reads strings made up of letters in the word ‘CHARIOT’ and recognizes these strings that contain the word ‘CAT’ as a substring.

Solution :

Meaning of various states:

q0 : Starting state.

q1 : First character C of ‘CAT’ is the preceding character.

q2 : First two characters CA of ‘CAT’ are the preceding two characters.

q3 : entire ‘CAT’ has been seen.

Design DFA that contain word 'CAT' using word 'CHARIOT'
State transition diagram
Design DFA that contain word 'CAT' using word 'CHARIOT'
State 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 CAT {

    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)=='A')
                Stateq0(str.substring(1));
            else if(str.charAt(0)=='H')
                Stateq0(str.substring(1));
            else if(str.charAt(0)=='I')
                Stateq0(str.substring(1));
            else if(str.charAt(0)=='O')
                Stateq0(str.substring(1));
            else if(str.charAt(0)=='T')
                Stateq0(str.substring(1));
            else if(str.charAt(0)=='R')
                Stateq0(str.substring(1));
            else if (str.charAt(0)=='C')
                Stateq1(str.substring(1));
        }
    }

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

        else {
            if(str.charAt(0)=='C')
                Stateq1(str.substring(1));
            else if(str.charAt(0)=='H')
                Stateq0(str.substring(1));
            else if(str.charAt(0)=='I')
                Stateq0(str.substring(1));
            else if(str.charAt(0)=='O')
                Stateq0(str.substring(1));
            else if(str.charAt(0)=='T')
                Stateq0(str.substring(1));
            else if(str.charAt(0)=='R')
                Stateq0(str.substring(1));
            else if(str.charAt(0)=='A')
                Stateq2(str.substring(1));
        }
    }

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

        else {
            if(str.charAt(0)=='A')
                Stateq0(str.substring(1));
            else if(str.charAt(0)=='H')
                Stateq0(str.substring(1));
            else if(str.charAt(0)=='I')
                Stateq0(str.substring(1));
            else if(str.charAt(0)=='O')
                Stateq0(str.substring(1));
            else if(str.charAt(0)=='C')
                Stateq1(str.substring(1));
            else if(str.charAt(0)=='R')
                Stateq0(str.substring(1));
            else if(str.charAt(0)=='T')
                Stateq3(str.substring(1));
        }
    }

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

        else {
            if(str.charAt(0)=='A')
                Stateq3(str.substring(1));
            else if(str.charAt(0)=='H')
                Stateq3(str.substring(1));
            else if(str.charAt(0)=='I')
                Stateq3(str.substring(1));
            else if(str.charAt(0)=='O')
                Stateq3(str.substring(1));
            else if(str.charAt(0)=='C')
                Stateq3(str.substring(1));
            else if(str.charAt(0)=='R')
                Stateq3(str.substring(1));
            else if(str.charAt(0)=='T')
                Stateq3(str.substring(1));
        }
    }

}

Output:

Enter the String
CHAICATCHAI
String 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. DFA for strings in which leftmost symbol differ from rightmost
  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

1 thought on “Design DFA that contain word ‘CAT’ using word ‘CHARIOT’”

  1. Generally I don’t read post on blogs, but I would like to say that
    this write-up very pressured me to take a look
    at and do so! Your writing style has been amazed
    me. Thanks, quite nice post.

Leave a Comment

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

x