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.
Continue reading Finite State Machine: Check Whether String Contains ‘abb’ or notCategory Archives: Snippets
Turing Machine for Well-Formedness of Parentheses in Java
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.
Push Down Automata in Java for Equal Number of a’s and b’s
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.
Continue reading Push Down Automata in Java for Equal Number of a’s and b’sIllustrating Epsilon Closure in Java
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.
Continue reading Illustrating Epsilon Closure in JavaFinite State Machine: Implementing Binary Adder in Java
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.
Continue reading Finite State Machine: Implementing Binary Adder in JavaMultithreading Example in Java
In this post, we implement a basic Multithreading example in Java. Multithreading allows multiple threads to execute concurrently within a single program, enabling tasks to run in parallel rather than one after another. Java has built-in support for multithreading through the Thread class and the Runnable interface.
What is Multithreading?
A thread is the smallest unit of execution within a process. When a program creates multiple threads, the operating system’s thread scheduler interleaves their execution — giving each thread a slice of CPU time in turn. This makes it appear as though they are running simultaneously (and on multi-core systems, they actually can be).
In this example, we create two threads by extending the Thread class and overriding its run() method. Each thread prints a label 4 times, pausing 500 ms between prints. Both threads run concurrently, so their output interleaves.
start()— Tells the JVM to create a new OS-level thread and invokerun()on it. Callingrun()directly would execute it on the current thread, not a new one.Thread.sleep(ms)— Pauses the current thread for the given number of milliseconds, allowing other threads to execute.InterruptedException— Must be caught when callingsleep(). It fires if another thread interrupts this one while it is sleeping.
Illustrating Working of FIFO Page Replacement Algorithm in C++
In this post, we implement the FIFO (First In, First Out) Page Replacement Algorithm in C++. When the OS needs to load a new page into memory but all frames are occupied, FIFO evicts the page that has been in memory the longest — the one that arrived first. It is one of the simplest page replacement strategies and serves as a baseline for comparing more sophisticated algorithms.
What is FIFO Page Replacement?
Physical memory is divided into frames. When a process references a page not currently in a frame (a page fault), it must be loaded. If all frames are full, an existing page must be evicted. FIFO chooses the oldest resident page for eviction, regardless of how frequently it has been used.
- Page Hit — Referenced page is already in a frame. No disk I/O needed.
- Page Fault (Miss) — Referenced page is not in any frame. Must load from disk.
- FIFO Queue — Tracks the order in which pages were loaded. Front = oldest; back = newest.
A notable weakness of FIFO is Bélady’s Anomaly — adding more frames can sometimes cause more page faults, counter-intuitively.
Continue reading Illustrating Working of FIFO Page Replacement Algorithm in C++