I think the complexity of the state machine depends on how we implemented it. If we use the old school FSM (with switch statements and if statements under one huge file) we are more likely encounter with the term "spaghettification".
If we implement an FSM that uses the abstract class (I think its called modular FSM) the complexity will be reduced a lot since each set of rules for each state will run only on their class scopes. This also gives us the power of adding new states and running parallel states at the same time. An example would be a global state "Attack" and the inner states of the Attack, like you described on your post. However, we might also end up with duplicated codes no matter how much we hate.