DEV Community: Binary Dose

The Chomsky Hierarchy: Why Regex Cannot Parse HTML

Binary Dose — Sat, 24 Oct 2026 17:01:42 +0000

The Chomsky Hierarchy

In 1956, Noam Chomsky classified all formal grammars into a strict 4-level mathematical hierarchy.

🏗️ The 4 Tiers

Type 3 (Regular Languages): Recognized by Finite Automata. Zero stack memory.
Type 2 (Context-Free Languages): Recognized by Pushdown Automata. Has a single LIFO stack for balanced delimiters.
Type 1 (Context-Sensitive Languages): Recognized by Linear Bounded Automata.
Type 0 (Recursively Enumerable): Recognized by Turing Machines with infinite tape.

Explore the full interactive curriculum on Binary Dose.

Why Does TCP Use a Sliding Window? (Flow Control vs BDP)

Binary Dose — Sat, 24 Oct 2026 13:48:51 +0000

Why Does TCP Use a Sliding Window?

Over high-latency networks, naive Stop-and-Wait throughput collapses because the physical pipe sits empty for most of the Round Trip Time (RTT).

⚡ The Bandwidth-Delay Product (BDP)

$$\text{BDP} = \text{Bandwidth} \times \text{RTT}$$

On a 10 Gbps transatlantic link with 100ms RTT, BDP = 125 MB! Stop-and-Wait wastes 99.9% of that capacity.

🧠 4 Buffer Window Zones

Zone 1 (ACKed): Safe to discard from RAM.
Zone 2 (In-Flight): Emitted, awaiting ACK.
Zone 3 (Usable): Permitted to send immediately.
Zone 4 (Blocked): Outside advertised window.

Read the full interactive visualizer on Binary Dose.

Announcing the Theory of Computation (TOC) Master Track on Binary Dose

Binary Dose — Sat, 24 Oct 2026 12:30:32 +0000

🚀 CoreDose Launch: Theory of Computation (TOC) Master Track

"Our goal is to provide the absolute best learning experience to our students so they grasp mental models in under 3 seconds."

We are thrilled to announce that the complete Theory of Computation (TOC) master curriculum is now LIVE and 100% free on Binary Dose!

📚 The 10-Module Curriculum Overview

Phase 1: Finite Automata & Regular Languages

Module 01: Alphabets, Strings, DFA Formalisms, Acceptance Criteria & Combinatorics
Module 02: Non-Deterministic Finite Automata (NFA), Epsilon-Closures & DFA Minimization
Module 03: Moore and Mealy Machine Architectures & Bidirectional State Conversions
Module 04: Regular Expressions, Algebraic Identities & Arden's Theorem

Phase 2: Grammars & Pushdown Automata

Module 05: Phrase Structure Grammars, The Chomsky Hierarchy & Type-3 Regular Grammars
Module 06: Pumping Lemma for Regular Languages, Non-Regularity Proofs & Memory Limits
Module 07: Context-Free Grammars, Ambiguity, Parse Trees & Normal Forms (CNF / GNF)
Module 08: Pushdown Automata (PDA), Instantaneous Descriptions & DCFL Boundaries

Phase 3: Computability & Complexity Theory

Module 09: Turing Machine 7-Tuple Model, Infinite Tape Mechanics, Multi-Tape Variants & Church-Turing Thesis
Module 10: The Halting Problem, Undecidability, Rice's Theorem, PCP, and Computational Complexity (Class P vs Class NP)

💡 What Makes Binary Dose Different?

Interactive State Transition Diagrams: Trace transitions and trap states in real time.
Deterministic Mathematical Proofs: Pumping lemmas and closure property matrices broken down into first principles.
Zero Paywalls: Always 100% open-access engineering education.

Explore the complete course right now:
👉 https://binarydose.in/coredose/toc

Why Do Database Indexes Slow Down INSERTs? (The B+ Tree Page Split Dilemma)

Binary Dose — Sat, 24 Oct 2026 10:46:36 +0000

Every junior engineer learns that adding an index to a database column makes SELECT queries blazing fast—reducing full table scans ((N)$) to logarithmic B+ Tree lookups ((\log N)$).

So why shouldn't we just index every single column in the table?

Because on an indexed table, a simple INSERT is never just an append. In high-throughput systems, over-indexing can spike write latency by 300% to 500%.

Here is what actually happens inside a database storage engine during an INSERT.

1. Unindexed Table: The O(1) Sequential Append

When a table has no secondary indexes, inserting a row is straightforward:

The database appends the raw row to the end of the current heap data page.
This is a fast, sequential write ((1)$ complexity).
Disk I/O is minimal, and Write-Ahead Log (WAL) records are simple.

2. Indexed Table: The Write Amplification Problem

When you add indexes (such as B+ Trees on email, created_at, or status), the database must maintain every single index in strictly sorted order.

Every single INSERT statement now triggers a 2-phase execution:

Heap Storage Write: The row is written to raw heap storage.
Index Traversal: The storage engine traverses the B+ Tree of every secondary index down from the root page to the target leaf page to find the exact insertion slot.
Key Shifting: Existing keys on that 8KB or 16KB leaf page must be shifted down to insert the new key in sorted order.

3. The Real Killer: B+ Tree Page Splits

What happens when the target 16KB leaf page is completely full?

The database cannot simply overwrite adjacent memory. It is forced to trigger an expensive Page Split:

Allocate New Page: The engine allocates a new 16KB disk page.
Migrate Keys: Exactly 50% of the keys from the full page are moved to the new page.
Update Parent Pointer: A new routing key and pointer are inserted into the parent node.
Cascading Splits: If the parent node is also full, the split cascades upward toward the root, increasing the height of the tree.
WAL Logging: Every modified page generates multiple Write-Ahead Log (WAL) records for durability.

The Result: A single INSERT statement turns into multiple random disk I/O operations and write amplification!

Key Takeaways for Backend Engineers

Indexes are not free: Every index you add speeds up reads at the direct expense of write throughput and storage bloat.
Avoid indexing high-cardinality volatile fields: If a column changes constantly and isn't frequently used in WHERE clauses, do not index it.
Batch Inserts: When loading bulk data, inserting in sorted order of the clustered index drastically reduces page splits.

🚀 Explore the Interactive Visualizer:
We built an interactive B+ Tree Page Split simulator and memory rail on Binary Dose to help engineers grasp storage engine internals in under 3 seconds.

👉 Read the Full Deep-Dive & Play with the Simulator on Binary Dose