It's interesting that both the question and the answer do focus on pattern matching. I maybe mistaken on this but that is really just one use of FSMs.

I've implement event-driven FSMs and to me the biggest "ah ah" moment was that it was trivial to make a list of valid (or non valid) state transitions. I used it in one particular case which was really complex (IMHO) to model and were my code was quickly becoming a gigantic mess. I ended up rewriting that part using an event-driven FSM and things became smooth.

Nowadays I don't like the 'S' in "FSM" that much anymore: I've moved to FP and can't really say I'm missing mutability.