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.