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!
* { 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!