A Finite State Machine (FSM) can determine whether a decimal integer is divisible by 3 without performing any division. The key insight is that a number is divisible by 3 if and only if the sum of its digits is divisible by 3. We can track the running digit-sum modulo 3 as we process each digit, mapping perfectly onto a 3-state FSM: State 0 (remainder 0), State 1 (remainder 1), and State 2 (remainder 2). After processing all digits, the machine is in State 0 if and only if the number is divisible by 3. The FSM also prints a state trace as it processes each digit.

A Finite State Machine (FSM) can be designed to recognise strings that end with a specific suffix. In this post, we build a 4-state FSM that accepts strings over the alphabet {a, b} which end with the suffix ‘abb’. Unlike the “contains” variant, here only the final state of the machine matters — the string is accepted if and only if the last three characters form ‘abb’. The FSM also prints a state trace showing each transition as it processes the input.

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.