DEV Community

Binary Dose
Binary Dose

Posted on Originally published at binarydose.in

The Chomsky Hierarchy: Why Regex Cannot Parse HTML

#algorithms #computerscience #programming #webdev

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.

Top comments (0)