I guess what is used there is more or less a toy example. I used state machines once in a game and had quite good experience with it, especially when things grew more complex.
A lot of these abstraction patterns only start to show their true powers when in use in software that grew big.
That being said, I probably wouldn't use state machines there, I would use a type system..
This approach seems to be simply implementing short-circuit boolean operators e.g. as soon as any AND condition is false, then false; as soon as any OR condition is true return true. The first example of evaluates every condition in a bottom up approach. While it's implemented as a FSM it doesn't need to be.
I think using ROBDDs (binary decision diagrams) or unrolling the AST into opcodes would be a more standard way of implementing optimisations.
* an explanation how to test the multiple heterogenous out-transitions of a state efficiently,
* the reason for the silent assumption that at most one out-transition of a state is followed, i.e. that this is not an NFA [0],
* most importantly, a comparison with Binary Decision Diagrams [1].
[0] https://en.wikipedia.org/wiki/Nondeterministic_finite_automa...
[1] https://en.wikipedia.org/wiki/Binary_decision_diagram