I’m just doing a module in formal languages & automata now but hadn’t yet made the connection that they were related to regular expressions. Neat!
Great read, very clearly explained & what a nice programming project too, writing a solver like that - would be great to stick a diagram-parsing front-end on it and then I could solve all my homework problems in double quick time.
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
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!
Great read, very clearly explained & what a nice programming project too, writing a solver like that - would be great to stick a diagram-parsing front-end on it and then I could solve all my homework problems in double quick time.