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!

I follow Vaguely Reassuring Finite-State Machines on Twitter and had not realized it had such depths. What a delightful article

Related: For doing the opposite, Ragel is able to translate regex into a graph, visually depicted courtesy of Graphviz.

https://en.wikipedia.org/wiki/Graphviz