Turning vaguely reassuring finite-state machines into regular expressions

Automata theory aficionado here. Regular languages are really neat! They have an air of being an "important" mathematical object, given how many different "natural" characterizations of them exist.

In a standard CS course you'll start out learning that regular expressions and finite state automata define the same class of languages. But they're also equivalent to:

- Languages generated by regular grammars (only rules of the form A -> a, A -> Ba, or A -> epsilon)

- Languages definable in monadic second-order (MSO) logic

- Languages "recognized" by a finite monoid (this algebraic appraoch to formal languages is super interesting and rich!)

- Language's whose Myhill-Nerode relation has finitely many equivalence classes

I recall doing a few of these conversions on paper in one of the written tests in my theoretical compsci exam.

Automata and languages are really neat. I find it beautiful that:

* { a^n | n in N } is regular;

* { a^n b^n | n in N } is not regular (exercise: use the pumping lemma to prove this) but is context-free, i.e. it can be recognised by a pushdown automaton (a finite state machine which can also use a single stack);

* { a^n b^n c^n | n in N } is not context-free (by a pumping lemma again), but it is context-sensitive, so can be recognised by a linear bounded automaton.

Oh, and "finite state machine with two stacks" is Turing-complete so any computable language has a recogniser of that form.

It's mad that you get such fundamentally interesting classes of machine just by generalising so simply in such natural ways!