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