The equivalence: everything coincides at "regular"

Parent: regular-languages

The regular languages are the class where completely independent definitions — from expressions, machines, grammars, logic, and algebra — all pick out the same sets. Each equivalence is worth its own article.

The coincidence

regex ⟺ finite automaton ⟺ right-linear grammar ⟺ finite Myhill–Nerode index ⟺ MSO-definable ⟺ recognized by a finite monoid.

The equivalences (one each)

• kleene-theorem — regex ⟺ finite automaton (Thompson's construction, subset construction, state elimination / Arden).
• myhill-nerode — finite suffix-index ⟺ regular; gives the unique minimal DFA and the cleanest non-regularity proofs.
• mso-and-automata — MSO logic = regular (Büchi–Elgot–Trakhtenbrot); the logic ↔ automata bridge.
• syntactic-monoid — recognizable by a finite monoid; the algebraic view (and star-free = aperiodic).

Why it's beautiful, not just tidy

Almost no other language class has this many independent faces. When a definition from logic and a definition from algebra and a definition from machines all land on the same object, you've found something structurally fundamental — regular = the fixed point where expressions, machines, grammars, logic, and algebra all agree. It's the first thing everyone learns and the last thing that stays simple.