"Plus the sort of people who can program a finite state machine probably "
That's the thing about FSM's.
You don't program them.You implement them. In hardware. That's where you get the speed from.
Of course you can implement an FSM interpreter that navigates through a state table.
Which is what YACC or Bison are.
Mine's the one with the old digital design text with the chapter on "Mealy-Moore" systems.