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.




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:
- Introduction to Finite Automata
- Deterministic Finite Automata (DFA)
- Number of 1’s is a multiple of 3 on {0,1} using DFA
- Number of 1’s is not multiple of 3 on {0,1} using DFA
- DFA for Number of 1’s is even/odd and number of 0’s is even/odd
- DFA for number of 0’s divisible by five and 1’s divisible by 3
- DFA for All string of length at most five
- DFA for All strings ending with abb
- DFA for strings in which leftmost symbol differ from rightmost
- Design DFA which accept a binary number divisible by 3
- Non-Deterministic finite Automata
- Design NFA to accept string containing the substring 0101
- Design NFA that accepts string ending with aab