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.

A Turing Machine is the most powerful model of computation, capable of simulating any algorithm. While the well-formedness of parentheses is typically solved with a stack, this post models it using the Turing Machine approach: we iteratively scan the tape (string) for the innermost matching pair (), replace them with a marker character, and repeat until either all characters are markers (accepted) or an unmatched symbol remains (rejected). This technique directly mirrors how a Turing Machine’s read/write head manipulates tape symbols.

A Pushdown Automaton (PDA) extends a Finite State Machine by adding a stack as auxiliary memory. This extra storage allows PDAs to recognize context-free languages that simple FSMs cannot handle. A classic example is the language aⁿBⁿ — strings consisting of exactly n copies of ‘a’ followed by n copies of ‘b’, for any n ≥ 1. The PDA pushes an ‘a’ onto the stack for every ‘a’ it reads, then pops one entry for every ‘b’. If the stack is empty exactly when all input is consumed, the string is accepted.

In the theory of computation, epsilon-closure (ε-closure) is a fundamental operation for converting a Non-deterministic Finite Automaton (NFA) with ε-transitions into an equivalent Deterministic Finite Automaton (DFA). The ε-closure of a state s is the set of all states reachable from s by following zero or more ε-transitions alone, without consuming any input symbol. In this post, we implement ε-closure computation in Java using a recursive depth-first approach.

A Finite State Machine (FSM) is a mathematical model of computation that transitions between a finite set of states based on input. One elegant application is a binary adder — where two binary strings are added bit-by-bit from right to left, with the FSM managing carry propagation between two states: no-carry (state 0) and carry (state 1). In this post, we implement this FSM-based binary adder in Java, complete with state transition functions and step-by-step output.