Type 3 — regular languages (no memory)

Parent: chomsky-hierarchy

The bottom tier: recognized by machines with no memory beyond a current state. What makes it special is that three independent formalisms — and several more — all define exactly this class. Each gets its own note; the coincidence is a note of its own.

The three formalisms

• regular-expressions — ∅, ε, symbols closed under union, concatenation, star.
• finite-automata — DFA / NFA: finitely many states, no auxiliary memory.
• regular-grammar — right-linear grammars A → aB | a.

They are all equivalent (Kleene, + Myhill–Nerode, + MSO logic, + finite monoids) — the equivalence and its constructions are their own article: regular-equivalences.

The one limitation

Pumping lemma (regular)

Every long enough word w in a regular language splits w=xyz with |xy|≤p, y≠ε, such that xyⁱz stays in the language for all i≥0.

Consequence: aⁿbⁿ is not regular — with no memory you can't count, so you can't match the two blocks. (Myhill–Nerode gives a cleaner proof — see regular-equivalences.) That limitation is exactly why you climb to a stack.

Facts

• Closure: union, concatenation, star, complement, intersection — a Boolean algebra.
• Decidability: membership, emptiness, equivalence — all decidable and efficient.
• Uses: lexers, grep, protocol/state machines.