A Finite State Machine (FSM) can efficiently detect whether a given string contains a specific pattern as a substring. In this post, we design an FSM with four states to check whether a string over the alphabet {a, b} contains the substring ‘abb’. The FSM uses a transition table to move between states as characters are read, and rejects the string once it finds ‘abb’. The machine enters a trap state upon detecting ‘abb’ and stays there regardless of further input.

FSM to Check if String Contains ‘abb’ in Java

import java.io.*;

public class FsmContainsAbb {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        /**
         * Transition table: transitionTable[currentState][inputSymbol] = nextState
         * Column 0 = input 'a', Column 1 = input 'b'
         *
         * State meanings:
         *   State 0 -- initial state, no progress toward 'abb'
         *   State 1 -- just seen 'a'
         *   State 2 -- just seen 'ab'
         *   State 3 -- just seen 'abb' (trap/detection state)
         */
        int[][] transitionTable = {
            {1, 0},  // State 0: on 'a' go to 1, on 'b' stay at 0
            {1, 2},  // State 1: on 'a' stay at 1, on 'b' go to 2
            {1, 3},  // State 2: on 'a' go to 1, on 'b' go to 3 (found 'abb'!)
            {3, 3}   // State 3: trap state -- once 'abb' is found, stay here
        };

        int currentState = 0;  // Start in the initial state

        System.out.println("Enter your string (alphabet: 'a' and 'b'):");
        String inputString = reader.readLine();

        // Process each character and follow the FSM transitions
        for (int i = 0; i < inputString.length(); i++) {
            char currentChar = inputString.charAt(i);
            if (currentChar == 'a') {
                currentState = transitionTable[currentState][0];  // 'a' uses column 0
            } else if (currentChar == 'b') {
                currentState = transitionTable[currentState][1];  // 'b' uses column 1
            }
        }

        // State 3 means 'abb' was found somewhere in the string
        if (currentState == 3) {
            System.out.println("String Rejected (contains 'abb')");
        } else {
            System.out.println("String Accepted (does not contain 'abb')");
        }
    }
}

How the Code Works

1. Transition table: transitionTable[s] gives the next state from state s on input character c (0 for ‘a’, 1 for ‘b’). The four states track how far along the pattern ‘abb’ we have matched.
2. State 0 is the initial state. Any ‘b’ before any ‘a’ keeps the machine here; an ‘a’ advances it to State 1.
3. State 1 means we just saw an ‘a’. Another ‘a’ keeps us at State 1; a ‘b’ advances to State 2.
4. State 2 means we saw ‘ab’. An ‘a’ resets to State 1 (new potential match starts); a ‘b’ completes ‘abb’ and enters State 3.
5. State 3 is the trap state. Once ‘abb’ is found, we never leave it regardless of further input.
6. Decision: After consuming the full string, if currentState == 3, the string contains ‘abb’ and is rejected; otherwise it is accepted.

Sample Output

Enter your string (alphabet: 'a' and 'b'):
aaaaababababababababa
String Accepted (does not contain 'abb')

Enter your string (alphabet: 'a' and 'b'):
ababababaaabbbababab
String Rejected (contains 'abb')

Output Explanation

1. For aaaaababababababababa: Every ‘b’ is followed only by ‘a’, so the machine alternates between State 1 and State 2 but never reaches State 3. Final state is 1 → Accepted.
2. For ababababaaabbbababab: After reaching the substring ‘abb’ within the sequence aabbb, the FSM enters State 3 and stays there for the rest of the input. Final state is 3 → Rejected.

See Also

• Finite State Machine: Check Whether String Ends with ‘abb’ or not
• Finite State Machine: Check Whether Number is Divisible by 3 or not
• Finite State Machine: Implementing Binary Adder in Java
• Push Down Automata: Equal Number of a’s and b’s in Java
• Turing Machine: Well-Formedness of Parenthesis in Java

Conclusion

This FSM cleanly demonstrates how a transition table can be used to recognize a pattern in a stream of characters in a single linear pass. The key insight is how the states encode partial match progress — a technique that underpins many real-world string matching algorithms and lexer generators. Try modifying the transition table to detect other patterns like ‘ab’, ‘ba’, or ‘aab’ as an exercise.